
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>7.树论例题.md · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="9.模板.html" />
    
    
    <link rel="prev" href="6.树论.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="1.图论.html">
            
                <a href="1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="2.图论例题.html">
            
                <a href="2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="3.散列表.html">
            
                <a href="3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.4" data-path="4.排序算法.html">
            
                <a href="4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="5.排序列题.html">
            
                <a href="5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.6" data-path="6.树论.html">
            
                <a href="6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="3.7" data-path="7.树论例题.html">
            
                <a href="7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.8" data-path="9.模板.html">
            
                <a href="9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="../算法/leetCode周赛题解.html">
            
                <a href="../算法/leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="../算法/1.时间复杂度.html">
            
                <a href="../算法/1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="../算法/2.深度优先搜索.html">
            
                <a href="../算法/2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="../算法/2.深度优先搜索题目集.html">
            
                <a href="../算法/2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.5" data-path="../算法/3.广度优先搜索.html">
            
                <a href="../算法/3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >7.树论例题.md</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><li><span class="title-icon "></span><a href="#&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;"><b></b>&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x6A59;&#x5B50;&#x6811;"><b></b>1.&#x6A59;&#x5B50;&#x6811;</a></li><li><span class="title-icon "></span><a href="#2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><b></b>2.&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a></li></ul><li><span class="title-icon "></span><a href="#&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;"><b></b>&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;</a></li><ul><li><span class="title-icon "></span><a href="#0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;"><b></b>0.&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;</a></li><li><span class="title-icon "></span><a href="#1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><b></b>1.&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a></li><li><span class="title-icon "></span><a href="#2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii"><b></b>2.&#x8DEF;&#x5F84;&#x603B;&#x548C; II</a></li><li><span class="title-icon "></span><a href="#3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii"><b></b>3.&#x8DEF;&#x5F84;&#x603B;&#x548C; III</a></li><li><span class="title-icon "></span><a href="#3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;"><b></b>3.&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;</a></li><li><span class="title-icon "></span><a href="#4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;"><b></b>4.&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;</a></li><li><span class="title-icon "></span><a href="#5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii"><b></b>5.&#x6253;&#x5BB6;&#x52AB;&#x820D; III</a></li><li><span class="title-icon "></span><a href="#6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;"><b></b>6.&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;"><b></b>&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5730;&#x9F20;&#x5B89;&#x5BB6;"><b></b>1.&#x5730;&#x9F20;&#x5B89;&#x5BB6;</a></li></ul><li><span class="title-icon "></span><a href="#&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;"><b></b>&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;</a></li><ul><li><span class="title-icon "></span><a href="#1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-"><b></b>1 &#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22; </a></li><li><span class="title-icon "></span><a href="#2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;"><b></b>2.&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;</a></li><li><span class="title-icon "></span><a href="#3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;"><b></b>3.&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;</a></li><li><span class="title-icon "></span><a href="#4&#x7FFB;&#x8F6C;&#x5BF9;"><b></b>4.&#x7FFB;&#x8F6C;&#x5BF9;</a></li></ul><li><span class="title-icon "></span><a href="#&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;"><b></b>&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;</a></li><li><span class="title-icon "></span><a href="#&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;"><b></b>&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x6A21;&#x677F;&#x9898;&#x76EE;"><b></b>1.&#x6A21;&#x677F;&#x9898;&#x76EE;</a></li><li><span class="title-icon "></span><a href="#2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-"><b></b>2.&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD; </a></li><li><span class="title-icon "></span><a href="#3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii"><b></b>3.&#x5355;&#x8BCD;&#x641C;&#x7D22; II</a></li><li><span class="title-icon "></span><a href="#4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;"><b></b>4.&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;</a></li><li><span class="title-icon "></span><a href="#5&#x56DE;&#x6587;&#x5BF9;"><b></b>5.&#x56DE;&#x6587;&#x5BF9;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h2 id="&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;"><a name="&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;" class="anchor-navigation-ex-anchor" href="#&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;" class="plugin-anchor" href="#&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00;&#x822C;&#x6811;&#x9898;&#x76EE;&#x96C6;</h2>
<h3 id="1&#x6A59;&#x5B50;&#x6811;"><a name="1&#x6A59;&#x5B50;&#x6811;" class="anchor-navigation-ex-anchor" href="#1&#x6A59;&#x5B50;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x6A59;&#x5B50;&#x6811;" class="plugin-anchor" href="#1&#x6A59;&#x5B50;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x6A59;&#x5B50;&#x6811;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201208232151.png" alt="image-20201208232151760"></p>
<pre><code>5 2
1 2 1
2 3 2
3 4 2
4 5 1


&#x8F93;&#x51FA;:
7
</code></pre><p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201208233503.png" alt="image-20201208233503734"></p>
<p><strong>&#x7B97;&#x6CD5;&#x9009;&#x62E9;</strong></p>
<p>&#x8FD9;&#x91CC;&#x9009;&#x62E9;&#x7528;dijkstra&#x6C42;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x957F;&#x5EA6;</p>
<p><strong>&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</strong></p>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">typedef</span> pair&lt;<span class="hljs-keyword">int</span>,<span class="hljs-keyword">int</span>&gt; ll;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> MAXN=<span class="hljs-number">1e5</span>+<span class="hljs-number">10</span>;
<span class="hljs-built_in">vector</span>&lt;ll&gt; graph[MAXN];
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dist(MAXN,<span class="hljs-number">0</span>);
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; vis(MAXN,<span class="hljs-number">0</span>);
priority_queue&lt;ll,<span class="hljs-built_in">vector</span>&lt;ll&gt;,less&lt;ll&gt;&gt; qu; <span class="hljs-comment">//&#x4F18;&#x5148;&#x961F;&#x5217;</span>
<span class="hljs-keyword">int</span> sumL=<span class="hljs-number">0</span>;<span class="hljs-comment">//&#x603B;&#x7684;&#x8FB9;&#x6743;</span>
<span class="hljs-keyword">int</span> maxL=<span class="hljs-number">0</span>; <span class="hljs-comment">//&#x79BB;&#x6E90;&#x70B9;&#x6700;&#x5927;&#x957F;&#x5EA6;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b,<span class="hljs-keyword">int</span> v)</span></span>{
    graph[a].push_back({b,v});
    graph[b].push_back({a,v});
    sumL+=v;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dijkstra</span><span class="hljs-params">(<span class="hljs-keyword">int</span> start)</span>
</span>{
    qu.push({<span class="hljs-number">0</span>,start});
    <span class="hljs-keyword">while</span>(!qu.empty())
    {
        <span class="hljs-keyword">int</span> cur=qu.top().second;
        qu.pop();
        <span class="hljs-keyword">if</span> (vis[cur])<span class="hljs-keyword">continue</span>;
        vis[cur]=<span class="hljs-literal">true</span>;
        maxL=max(maxL,dist[cur]);
        <span class="hljs-comment">//&#x5BF9;&#x6BCF;&#x4E00;&#x4E2A;&#x90BB;&#x63A5;&#x8FB9;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;graph[cur].size();i++)
        {
            ll child= graph[cur][i];
            <span class="hljs-keyword">if</span>(!vis[child.first])
            {
                <span class="hljs-keyword">if</span>(dist[cur]+child.second&gt;dist[child.first])
                {
                    dist[child.first]=dist[cur]+child.second;
                    qu.push({dist[child.first],child.first});
                }
            }
        }
    }
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    <span class="hljs-keyword">int</span> n,start;
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;start;
    <span class="hljs-keyword">int</span> a,b,v;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n<span class="hljs-number">-1</span>;i++)
    {
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;v;
        add(a,b,v);
    }
    dijkstra(start);
    <span class="hljs-built_in">cout</span>&lt;&lt;sumL*<span class="hljs-number">2</span>-maxL;
}
</code></pre>
<h3 id="2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><a name="2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="anchor-navigation-ex-anchor" href="#2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="plugin-anchor" href="#2&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>2.<a href="https://leetcode-cn.com/problems/unique-binary-search-trees/" target="_blank">&#x4E0D;&#x540C;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210193431.png" alt="image-20201210193431504"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x672C;&#x9898;&#x4E3B;&#x8981;&#x8003;&#x5BDF;dp,bst&#x7684;&#x6027;&#x8D28;</p>
<p>&#x4EE5;i&#x4E3A;&#x6839;&#x8282;&#x70B9;,&#x5219;&#x5176;&#x5DE6;&#x5B50;&#x6811;&#x4E3A;[0,i-1],&#x53F3;&#x5B50;&#x6811;&#x4E3A;[i+1,n]</p>
<p>&#x6240;&#x4EE5;num[i]=dp[i-1]+dp[n-i] (i=0,1,2,....n);</p>
<p>dp&#x8FB9;&#x754C;&#x662F;dp[0]=1</p>
<p>&#x4EE3;&#x7801;:</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">numTrees</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dp(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>);
    dp[<span class="hljs-number">0</span>]=<span class="hljs-number">1</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;=n ; ++i) {
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=i;j++){
            dp[i]+=dp[j<span class="hljs-number">-1</span>]*dp[i-j];
        }
    }
    <span class="hljs-keyword">return</span> dp[n];
}
};
</code></pre>
<h2 id="&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;"><a name="&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;" class="anchor-navigation-ex-anchor" href="#&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;" class="plugin-anchor" href="#&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x6811;&#x7684;&#x9012;&#x5F52;&#x7C7B;&#x578B;</h2>
<h3 id="0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;"><a name="0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;" class="anchor-navigation-ex-anchor" href="#0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;" class="plugin-anchor" href="#0&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;"><i class="fa fa-link" aria-hidden="true"></i></a>0.<a href="https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/" target="_blank">&#x4E8C;&#x53C9;&#x6811;&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;&#x2B50;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210201548.png" alt="image-20201210201547921"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x9012;&#x5F52;&#x7684;&#x5E38;&#x89C1;&#x601D;&#x8DEF;:</p>
<ul>
<li>&#x76F8;&#x4FE1;&#x4E00;&#x4E2A;&#x51FD;&#x6570;,&#x80FD;&#x63D0;&#x4F9B;&#x5C06;&#x4EE5;root&#x4E3A;&#x6839;&#x7684;&#x6811;,&#x5C55;&#x5F00;&#x4E3A;&#x94FE;&#x8868;</li>
<li>&#x4E8E;&#x662F;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x501F;&#x52A9;&#x6B64;&#x51FD;&#x6570;&#x5F97;&#x5230;&#x5DE6;&#x53F3;&#x4E24;&#x6839;&#x94FE;&#x8868;</li>
<li>&#x6700;&#x540E;&#x53D8;&#x5316;&#x4E00;&#x4E0B;&#x5373;&#x53EF;</li>
<li>&#x4E00;&#x5B9A;&#x8981;&#x628A;&#x9012;&#x5F52;&#x60F3;&#x8C61;&#x6210;&#x4E00;&#x4E2A;&#x62BD;&#x8C61;&#x7684;&#x8FC7;&#x7A0B;,&#x5C31;&#x5F53;&#x4F5C;&#x6211;&#x4EEC;&#x5DF2;&#x7ECF;&#x6709;&#x4E24;&#x6839;&#x94FE;&#x8868;&#x4E86;,&#x8981;&#x505A;&#x7684;&#x65E0;&#x975E;&#x662F;&#x904D;&#x5386;&#x5230;&#x5DE6;&#x8FB9;&#x90A3;&#x6839;&#x94FE;&#x8868;&#x7684;&#x6700;&#x53F3;&#x8FB9;&#x90A3;&#x4E2A;&#x8282;&#x70B9;,&#x7136;&#x540E;&#x628A;&#x53F3;&#x8FB9;&#x90A3;&#x6839;&#x94FE;&#x8868;&#x63A5;&#x4E0A;&#x5373;&#x53EF;</li>
</ul>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-function">node <span class="hljs-title">dfs</span><span class="hljs-params">(node root)</span></span>{
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;
    node left=dfs(root-&gt;left);
    node right=dfs(root-&gt;right);
    root-&gt;right=left;
    <span class="hljs-comment">//&#x904D;&#x5386;&#x5230;&#x6700;&#x53F3;&#x8FB9;&#x4E00;&#x4E2A;&#x8282;&#x70B9;</span>
    node temp=root;
    <span class="hljs-keyword">while</span>(temp-&gt;right){
        temp=temp-&gt;right;
    }
    temp-&gt;right=right;
    root-&gt;left=<span class="hljs-literal">NULL</span>;
    <span class="hljs-keyword">return</span> root;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">flatten</span><span class="hljs-params">(TreeNode* root)</span> </span>{
    dfs(root);
}
};
</code></pre>
<h3 id="1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><a name="1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="anchor-navigation-ex-anchor" href="#1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="plugin-anchor" href="#1&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>1.<a href="https://leetcode-cn.com/problems/validate-binary-search-tree/" target="_blank">&#x9A8C;&#x8BC1;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210194838.png" alt="image-20201210194838614"></p>
<p>&#x5BF9;&#x4E8E;BST,&#x65E0;&#x975E;&#x5DE6;&#x5B50;&#x6811;&#x6BD4;&#x5F53;&#x524D;&#x5C0F;,&#x53F3;&#x5B50;&#x6811;&#x6BD4;&#x5F53;&#x524D;&#x5927;,&#x9003;&#x4E0D;&#x8FC7;&#x8FD9;&#x4E2A;&#x6027;&#x8D28;,&#x5173;&#x4E8E;BST&#x7684;&#x90FD;&#x53EF;&#x4EE5;&#x5F80;&#x8FD9;&#x4E2A;&#x65B9;&#x5411;&#x5957;</p>
<p>&#x6240;&#x4EE5;,&#x5F88;&#x5BB9;&#x6613;&#x5F97;&#x51FA;&#x9012;&#x5F52;&#x7684;&#x601D;&#x8DEF;:</p>
<pre><code class="lang-c++"><span class="hljs-comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */</span>
<span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-function"><span class="hljs-keyword">bool</span>  <span class="hljs-title">dfs</span><span class="hljs-params">(node root,<span class="hljs-keyword">long</span> lower,<span class="hljs-keyword">long</span> upper)</span></span>{
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
    <span class="hljs-keyword">int</span> val=root-&gt;val;
    <span class="hljs-keyword">if</span>(val&lt;=lower||val&gt;=upper)<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    <span class="hljs-keyword">return</span> dfs(root-&gt;left,lower,val)&amp;&amp;dfs(root-&gt;right,val,upper);

}
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode* root)</span> </span>{
    <span class="hljs-keyword">return</span> dfs(root,LONG_MIN,LONG_MAX);
}
};
</code></pre>
<h3 id="2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii"><a name="2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii" class="anchor-navigation-ex-anchor" href="#2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii" class="plugin-anchor" href="#2&#x8DEF;&#x5F84;&#x603B;&#x548C;-ii"><i class="fa fa-link" aria-hidden="true"></i></a>2.<a href="https://leetcode-cn.com/problems/path-sum-ii/" target="_blank">&#x8DEF;&#x5F84;&#x603B;&#x548C; II</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210201156.png" alt="image-20201210201156416"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x8FD9;&#x662F;&#x4E00;&#x9053;&#x5F88;&#x5E38;&#x89C1;&#x7684;dfs&#x56DE;&#x6714;&#x7C7B;&#x578B;&#x7684;&#x9898;&#x76EE;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">struct</span> TreeNode{
    <span class="hljs-keyword">int</span> val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(<span class="hljs-number">0</span>), left(<span class="hljs-literal">nullptr</span>), right(<span class="hljs-literal">nullptr</span>) {}
    TreeNode(<span class="hljs-keyword">int</span> x) : val(x), left(<span class="hljs-literal">nullptr</span>), right(<span class="hljs-literal">nullptr</span>) {}
};
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; result;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node root,<span class="hljs-keyword">int</span> cur,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; arr)</span>
</span>{
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">int</span> val=root-&gt;val;
    cur-=val;
    arr.push_back(val);
    <span class="hljs-keyword">if</span> (!root-&gt;left&amp;&amp;!root-&gt;right&amp;&amp;cur==<span class="hljs-number">0</span>)
    {
        result.push_back(arr);
        <span class="hljs-comment">//&#x6CE8;&#x610F;&#x56DE;&#x6714; </span>
        arr.pop_back();
        <span class="hljs-keyword">return</span>;
    }
    dfs(root-&gt;left,cur,arr);
    dfs(root-&gt;right,cur,arr);
            <span class="hljs-comment">//&#x6CE8;&#x610F;&#x56DE;&#x6714; </span>
    arr.pop_back();
}
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; pathSum(TreeNode* root, <span class="hljs-keyword">int</span> sum) {
    dfs (root,sum,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;{});
    <span class="hljs-keyword">return</span> result;
}
</code></pre>
<h3 id="3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii"><a name="3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii" class="anchor-navigation-ex-anchor" href="#3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii" class="plugin-anchor" href="#3&#x8DEF;&#x5F84;&#x603B;&#x548C;-iii"><i class="fa fa-link" aria-hidden="true"></i></a>3.<a href="https://leetcode-cn.com/problems/path-sum-iii/" target="_blank">&#x8DEF;&#x5F84;&#x603B;&#x548C; III</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201211150229.png" alt="image-20201211150229362"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x8FD9;&#x4E2A;&#x9898;&#x76EE;&#x5C31;&#x662F;&#x5BF9;&#x6BCF;&#x4E2A;&#x9876;&#x70B9;,&#x6709;&#x4E24;&#x79CD;&#x60C5;&#x51B5;:</p>
<ul>
<li>&#x7EE7;&#x627F;&#x4E0A;&#x4E00;&#x4E2A;&#x9876;&#x70B9;,&#x67E5;&#x770B;&#x5F53;&#x524D;&#x7684;&#x503C;&#x662F;&#x5426;&#x548C;&#x5269;&#x4E0B;&#x7684;target&#x76F8;&#x540C;</li>
<li>&#x4F20;&#x9012;&#x81F3;&#x5DE6;&#x53F3;&#x9876;&#x70B9;,&#x5728;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;&#x4E2D;&#x5BFB;&#x627E;&#x8DEF;&#x5F84;</li>
</ul>
<p>&#x53E6;&#x5916;,dfs&#x542B;&#x4E49;:</p>
<p>&#x4EE5;&#x5F53;&#x524D;&#x6839;&#x4E3A;&#x9876;&#x70B9;,&#x5BFB;&#x627E;&#x76EE;&#x6807;&#x4E3A;sum&#x7684;&#x8DEF;&#x5F84;</p>
<p>dfs&#x51FD;&#x6570;&#x9700;&#x8981;&#x5BF9;&#x6BCF;&#x4E2A;&#x9876;&#x70B9;&#x90FD;&#x8C03;&#x7528;&#x4E00;&#x6B21;</p>
<pre><code class="lang-c++"><span class="hljs-comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>
<span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node root,<span class="hljs-keyword">int</span> sum)</span></span>{
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> val=root-&gt;val;
    <span class="hljs-comment">//&#x5F53;&#x524D;&#x70B9;</span>
    <span class="hljs-keyword">if</span>(val==sum){
        ans++;
    }
    <span class="hljs-comment">//&#x5DE6;&#x53F3;</span>
    ans+=dfs(root-&gt;left,sum-val);
    ans+=dfs(root-&gt;right,sum-val);
    <span class="hljs-keyword">return</span> ans;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">pathSum</span><span class="hljs-params">(TreeNode* root, <span class="hljs-keyword">int</span> sum)</span> </span>{
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">return</span> dfs(root,sum)+pathSum(root-&gt;left,sum)+pathSum(root-&gt;right,sum);
}
};
</code></pre>
<h3 id="3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;"><a name="3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;" class="anchor-navigation-ex-anchor" href="#3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;" class="plugin-anchor" href="#3&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;"><i class="fa fa-link" aria-hidden="true"></i></a>3.<a href="https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/" target="_blank">&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x548C;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210204108.png" alt="image-20201210204108512"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210204116.png" alt="image-20201210204116338"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x540C;&#x6837;&#x6839;&#x636E;&#x7B2C;&#x4E00;&#x9898;&#x7684;&#x601D;&#x8DEF;:</p>
<ul>
<li>&#x76F8;&#x4FE1;&#x4E00;&#x4E2A;&#x51FD;&#x6570;dfs,&#x5B83;&#x53EF;&#x4EE5;&#x8FD4;&#x56DE;&#x4EE5;root&#x4E3A;&#x6839;&#x8282;&#x70B9;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;</li>
<li>&#x4E5F;&#x5373;&#x6211;&#x4EEC;&#x5C31;&#x53EF;&#x4EE5;&#x5F97;&#x5230;&#x5DE6;&#x53F3;&#x4E24;&#x9897;&#x6811;&#x5404;&#x81EA;&#x7684;&#x6700;&#x5927;&#x8DEF;&#x5F84;,&#x90A3;&#x5BF9;&#x4E8E;&#x5F53;&#x524D;&#x8282;&#x70B9;root,&#x5176;&#x6700;&#x5927;&#x8DEF;&#x5F84;&#x5C31;&#x662F;left+cur+right,&#x5E76;&#x66F4;&#x65B0;&#x7B54;&#x6848;</li>
<li>&#x4F46;&#x662F;&#x8FD4;&#x56DE;&#x7684;,&#x662F;&#x5DE6;&#x53F3;&#x6700;&#x5927;&#x7684;&#x8DEF;&#x5F84;+cur,&#x800C;&#x4E0D;&#x662F;&#x8FD4;&#x56DE;&#x6700;&#x5927;&#x8DEF;&#x5F84;</li>
</ul>
<pre><code class="lang-c++"><span class="hljs-comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>
<span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-keyword">int</span> answer=INT_MIN;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node root)</span>
</span>{
    <span class="hljs-keyword">if</span> (!root)<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> left=dfs(root-&gt;left);
    <span class="hljs-comment">//&#x5982;&#x679C;&#x5DE6;&#x53F3;&#x5C0F;&#x4E8E;0,&#x5219;&#x76F4;&#x63A5;&#x629B;&#x5F03;&#x5DE6;&#x53F3;&#x5373;&#x53EF;,&#x4E5F;&#x5373;&#x8D4B;&#x503C;&#x4E3A;0 </span>
    <span class="hljs-keyword">if</span> (left&lt;<span class="hljs-number">0</span>)left=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> right=dfs(root-&gt;right);
    <span class="hljs-keyword">if</span>(right&lt;<span class="hljs-number">0</span>)right=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> val=root-&gt;val;
    <span class="hljs-comment">//&#x8DDF;&#x65B0;&#x7B54;&#x6848; </span>
    answer=max(answer,left+right+val);
    <span class="hljs-comment">//&#x8FD4;&#x56DE;&#x5DE6;&#x53F3;&#x6700;&#x5927;+cur </span>
    <span class="hljs-keyword">return</span> max(left,right)+val;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxPathSum</span><span class="hljs-params">(TreeNode* root)</span> 
</span>{
     dfs(root);
     <span class="hljs-keyword">return</span> answer;
}
};
</code></pre>
<h3 id="4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;"><a name="4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;" class="anchor-navigation-ex-anchor" href="#4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;" class="plugin-anchor" href="#4&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;"><i class="fa fa-link" aria-hidden="true"></i></a>4.<a href="https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/" target="_blank">&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x8FD1;&#x516C;&#x5171;&#x7956;&#x5148;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210205525.png" alt="image-20201210205525646"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201210205531.png" alt="image-20201210205531854"></p>
<p>&#x8FD9;&#x79CD;&#x9898;&#x76EE;&#x4E3B;&#x8981;&#x5206;&#x6E05;&#x695A;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#x5373;&#x53EF;</p>
<pre><code class="lang-c++"><span class="hljs-function">TreeNode* <span class="hljs-title">lowestCommonAncestor</span><span class="hljs-params">(TreeNode* root, TreeNode* p, TreeNode* q)</span> </span>{
    <span class="hljs-keyword">if</span> (!root)<span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;
    <span class="hljs-comment">//&#x5982;&#x679C;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x548C;p,q&#x67D0;&#x4E00;&#x4E2A;&#x76F8;&#x7B49;,&#x8BF4;&#x660E;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x5C31;&#x662F;&#x8981;&#x627E;&#x7684;&#x70B9;</span>
    <span class="hljs-keyword">if</span> (root==p||root==q)<span class="hljs-keyword">return</span> root;
    <span class="hljs-comment">//&#x4ECE;&#x5DE6;&#x53F3;&#x4E2D;&#x5BFB;&#x627E;</span>
    node left=lowestCommonAncestor(root-&gt;left,p,q);
    node right=lowestCommonAncestor(root-&gt;right,p,q);
    <span class="hljs-comment">//&#x90FD;&#x4E0D;&#x4E3A;&#x7A7A;,&#x8BF4;&#x660E;p,q&#x5206;&#x6563;&#x5728;&#x5DE6;&#x53F3;&#x4E2D;,&#x5F53;&#x524D;&#x4E3A;&#x7236;&#x8282;&#x70B9;</span>
    <span class="hljs-keyword">if</span> (left&amp;&amp;right)<span class="hljs-keyword">return</span> root;
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> left?left:right;
}
</code></pre>
<h3 id="5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii"><a name="5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii" class="anchor-navigation-ex-anchor" href="#5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii" class="plugin-anchor" href="#5&#x6253;&#x5BB6;&#x52AB;&#x820D;-iii"><i class="fa fa-link" aria-hidden="true"></i></a>5.<a href="https://leetcode-cn.com/problems/house-robber-iii/" target="_blank">&#x6253;&#x5BB6;&#x52AB;&#x820D; III</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201211145043.png" alt="image-20201211145043403"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x8FD9;&#x662F;&#x4E00;&#x9053;&#x9012;&#x5F52;+dp&#x601D;&#x60F3;&#x7684;&#x9898;&#x76EE;</p>
<p>&#x72B6;&#x6001;&#x65E0;&#x975E;&#x4E24;&#x4E2A;:</p>
<ul>
<li>&#x5982;&#x679C;&#x62A2;&#x5F53;&#x524D;&#x7684;&#x8282;&#x70B9;,&#x5219;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;&#x4E0D;&#x80FD;&#x78B0;</li>
<li>&#x4E0D;&#x62A2;&#x5F53;&#x524D;&#x70B9;,&#x5219;&#x53EF;&#x4EE5;&#x78B0;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;</li>
</ul>
<p>&#x63A5;&#x7740;,&#x9012;&#x5F52;&#x7684;&#x601D;&#x60F3;,&#x76F8;&#x4FE1;&#x4E00;&#x4E2A;&#x51FD;&#x6570;,&#x5176;&#x53EF;&#x4EE5;&#x8FD4;&#x56DE;&#x4EE5;&#x4E00;&#x4E2A;root&#x4E3A;&#x6839;&#x7684;&#x70B9;&#x6240;&#x80FD;&#x62A2;&#x7684;&#x6700;&#x5927;&#x4F73;&#x503C;</p>
<pre><code class="lang-c++"><span class="hljs-comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */</span>
<span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-comment">//&#x5907;&#x5FD8;&#x5F55;</span>
<span class="hljs-built_in">map</span>&lt;node,<span class="hljs-keyword">int</span>&gt; dict;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node root)</span>
</span>{
    <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(dict.find(root)!=dict.end())
        <span class="hljs-keyword">return</span> dict[root];
    <span class="hljs-comment">//&#x5982;&#x679C;&#x62A2;&#x5F53;&#x524D;&#x70B9;,&#x5219;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;&#x70B9;&#x4E0D;&#x80FD;&#x62A2; </span>
    <span class="hljs-keyword">int</span> do_it= root-&gt;val;
    <span class="hljs-keyword">if</span>(root-&gt;left)do_it+=dfs(root-&gt;left-&gt;left)+dfs(root-&gt;left-&gt;right);
    <span class="hljs-keyword">if</span>(root-&gt;right)do_it+=dfs(root-&gt;right-&gt;left)+dfs(root-&gt;right-&gt;right);
    <span class="hljs-comment">//&#x4E0D;&#x62A2;&#x5F53;&#x524D;&#x70B9;,&#x53EA;&#x80FD;&#x62A2;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;&#x70B9; </span>
    <span class="hljs-keyword">int</span> no_do=dfs(root-&gt;left)+dfs(root-&gt;right);    
    <span class="hljs-keyword">int</span> result= max(do_it,no_do);
    dict[root]=result;
    <span class="hljs-keyword">return</span> result;
} 
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">rob</span><span class="hljs-params">(TreeNode* root)</span> </span>{
    <span class="hljs-keyword">return</span> dfs(root);
}

};
</code></pre>
<h3 id="6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;"><a name="6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;" class="anchor-navigation-ex-anchor" href="#6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;" class="plugin-anchor" href="#6&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;"><i class="fa fa-link" aria-hidden="true"></i></a>6.<a href="https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs/" target="_blank">&#x597D;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5BF9;&#x7684;&#x6570;&#x91CF;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201211154026.png" alt="image-20201211154025960"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201211154034.png" alt="image-20201211154034087"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x57FA;&#x672C;&#x601D;&#x8DEF;&#x5982;&#x4E0B;:</p>
<ul>
<li>&#x627E;&#x5230;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x7684;&#x6240;&#x6709;&#x5DE6;&#x53F3;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x8DDD;&#x79BB;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x7684;&#x8DDD;&#x79BB;</li>
<li>&#x5BF9;&#x4E24;&#x4E2A;&#x6570;&#x7EC4;&#x8FDB;&#x884C;&#x4E24;&#x4E24;&#x5339;&#x914D;,&#x770B;&#x662F;&#x5426;&#x5728;distance&#x8303;&#x56F4;&#x5185;</li>
</ul>
<pre><code class="lang-c++"><span class="hljs-keyword">struct</span> TreeNode{
    <span class="hljs-keyword">int</span> val;
    TreeNode *left;
    TreeNode * right;
    TreeNode(<span class="hljs-keyword">int</span> x):val(x),left(<span class="hljs-literal">NULL</span>),right(<span class="hljs-literal">NULL</span>){
    }
};
<span class="hljs-keyword">typedef</span> TreeNode * node;
<span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dfs(node root,<span class="hljs-keyword">int</span> top){
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; result{};
    <span class="hljs-keyword">if</span>(!root)<span class="hljs-keyword">return</span>  result;
    <span class="hljs-comment">//&#x5982;&#x679C;&#x5F53;&#x524D;&#x662F;&#x53F6;&#x5B50;&#x8282;&#x70B9;,&#x5C31;&#x8FD4;&#x56DE;&#x5F53;&#x524D;&#x8DDD;&#x79BB;1 </span>
    <span class="hljs-keyword">if</span>(!root-&gt;left&amp;&amp;!root-&gt;right)
    {
        result.push_back(<span class="hljs-number">1</span>);
        <span class="hljs-keyword">return</span> result;
    } 
    <span class="hljs-comment">//&#x83B7;&#x53D6;&#x5DE6;&#x53F3;&#x7684;&#x53F6;&#x5B50;&#x6570;&#x7EC4; </span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; left=dfs(root-&gt;left,top);
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; right=dfs(root-&gt;right,top);;
    <span class="hljs-keyword">if</span>(left.size()&gt;<span class="hljs-number">0</span>&amp;&amp;right.size()&gt;<span class="hljs-number">0</span>)
    {
        <span class="hljs-comment">//&#x4E24;&#x4E24;&#x5339;&#x914D; </span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> l:left)
            {
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> r:right)
                {
                    <span class="hljs-keyword">if</span>(l+r&lt;=top)
                    {
                        ans++;
                    }
                }
            }
    }
    <span class="hljs-comment">//&#x6784;&#x5EFA;&#x53F6;&#x5B50;&#x6570;&#x7EC4; </span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> l:left)
    {
        <span class="hljs-keyword">if</span>(l+<span class="hljs-number">1</span>&gt;top)<span class="hljs-keyword">continue</span>;
        result.push_back(l+<span class="hljs-number">1</span>);
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> r:right){
        <span class="hljs-keyword">if</span>(r+<span class="hljs-number">1</span>&gt;top)<span class="hljs-keyword">continue</span>;
        result.push_back(r+<span class="hljs-number">1</span>);
    }
    <span class="hljs-keyword">return</span> result;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">countPairs</span><span class="hljs-params">(TreeNode* root, <span class="hljs-keyword">int</span> distance)</span> </span>{
    dfs(root,distance);
    <span class="hljs-keyword">return</span> ans;   
}
</code></pre>
<h2 id="&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;"><a name="&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;" class="plugin-anchor" href="#&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5217;&#x9898;</h2>
<h3 id="1&#x5730;&#x9F20;&#x5B89;&#x5BB6;"><a name="1&#x5730;&#x9F20;&#x5B89;&#x5BB6;" class="anchor-navigation-ex-anchor" href="#1&#x5730;&#x9F20;&#x5B89;&#x5BB6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5730;&#x9F20;&#x5B89;&#x5BB6;" class="plugin-anchor" href="#1&#x5730;&#x9F20;&#x5B89;&#x5BB6;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5730;&#x9F20;&#x5B89;&#x5BB6;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201208235416.png" alt="image-20201208235416703"></p>
<pre><code>&#x8F93;&#x5165;&#x793A;&#x4F8B;
5
-1 1 -1
1 2 3
-1 3 -1
2 4 5
-1 5 -1

&#x8F93;&#x51FA;:
3
</code></pre><p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x8003;&#x70B9;:BST,BST&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x9012;&#x589E;</p>
<p>&#x5148;&#x6784;&#x5EFA;&#x4E00;&#x68F5;&#x6811;,&#x5229;&#x7528;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x5224;&#x65AD;&#x8BE5;&#x5E8F;&#x5217;&#x662F;&#x5426;&#x9012;&#x589E;&#x5373;&#x53EF;</p>
<h2 id="&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;"><a name="&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;" class="anchor-navigation-ex-anchor" href="#&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;" class="plugin-anchor" href="#&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x7EBF;&#x72B6;&#x6811;&#x5217;&#x9898;</h2>
<h3 id="1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-"><a name="1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-" class="anchor-navigation-ex-anchor" href="#1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-" class="plugin-anchor" href="#1-&#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22;-"><i class="fa fa-link" aria-hidden="true"></i></a><a href="https://leetcode-cn.com/problems/range-sum-query-mutable/" target="_blank">1 &#x533A;&#x57DF;&#x548C;&#x68C0;&#x7D22; </a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203170758.png" alt="image-20201203170758373"></p>
<p>&#x6A21;&#x677F;&#x9898;:</p>
<pre><code class="lang-c++">
<span class="hljs-comment">//&#x7EBF;&#x6BB5;&#x6811;&#x6A21;&#x677F;</span>
<span class="hljs-keyword">class</span> SegmentTree{
<span class="hljs-keyword">public</span>:
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ls k&lt;&lt;1</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span>  rs k&lt;&lt;1|1</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; tree;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; lazy;
    SegmentTree(<span class="hljs-keyword">int</span> size)
    {
        tree=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(size*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        lazy=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(size*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
    }
    SegmentTree()
    {

    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;nums)</span>
    </span>{
        <span class="hljs-keyword">if</span>(l==r)
            tree[k]=nums[l];
        <span class="hljs-keyword">else</span>
        {
            <span class="hljs-keyword">int</span> m=l+(r-l)/<span class="hljs-number">2</span>;
            build(ls,l,m,nums);
            build(rs,m+<span class="hljs-number">1</span>,r,nums);
            pushUp(k);
        }
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span>
    </span>{
        tree[k]=tree[ls]+tree[rs];
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> p,<span class="hljs-keyword">int</span> v )</span>
    </span>{
        <span class="hljs-keyword">if</span>(l==r)
            tree[k]=v;
        <span class="hljs-keyword">else</span>
        {
            <span class="hljs-keyword">int</span> m = l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(p&lt;=m)
                update(l,m,ls,p,v);
             <span class="hljs-keyword">if</span>(p&gt;m)
                update(m+<span class="hljs-number">1</span>,r,rs,p,v);
            pushUp(k);
        }
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">query</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> L,<span class="hljs-keyword">int</span> R,<span class="hljs-keyword">int</span> k)</span>
    </span>{
        <span class="hljs-keyword">if</span>(l&gt;=L&amp;&amp;r&lt;=R)
        {
            <span class="hljs-keyword">return</span> tree[k];
        }
        <span class="hljs-keyword">else</span>
        {
            <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
            <span class="hljs-keyword">int</span> m=l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">int</span> left=<span class="hljs-number">0</span>,right=<span class="hljs-number">0</span>;
            <span class="hljs-keyword">if</span>(L&lt;=m)
                left=query(l,m,L,R,ls);
             <span class="hljs-keyword">if</span>(R&gt;m)
                right=query(m+<span class="hljs-number">1</span>,r,L,R,rs);
            <span class="hljs-keyword">return</span> left+right;
        }
    }
};
<span class="hljs-keyword">class</span> NumArray {
<span class="hljs-keyword">public</span>:
    SegmentTree tree;
    <span class="hljs-keyword">int</span> num;
    NumArray(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums) {
        <span class="hljs-keyword">int</span> size=nums.size();
        <span class="hljs-keyword">if</span>(size==<span class="hljs-number">0</span>)<span class="hljs-keyword">return</span>;
        <span class="hljs-keyword">this</span>-&gt;num=size<span class="hljs-number">-1</span>;
        <span class="hljs-keyword">this</span>-&gt;tree=SegmentTree(size);
        tree.build(<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,num,nums);
    }

    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> val)</span> </span>{
        tree.update(<span class="hljs-number">0</span>,num,<span class="hljs-number">1</span>,i,val);
    }

    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sumRange</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>{
        <span class="hljs-keyword">return</span> tree.query(<span class="hljs-number">0</span>,num,i,j,<span class="hljs-number">1</span>);
    }
};
</code></pre>
<h3 id="2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;"><a name="2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;" class="anchor-navigation-ex-anchor" href="#2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;" class="plugin-anchor" href="#2&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a>2.<a href="https://leetcode-cn.com/problems/count-of-range-sum/" target="_blank">&#x533A;&#x95F4;&#x548C;&#x7684;&#x4E2A;&#x6570;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212114300.png" alt="image-20201212114259984"></p>
<p><strong>&#x9898;&#x76EE;&#x89E3;&#x6790;</strong></p>
<p>&#x7ED9;&#x51FA;&#x4E00;&#x4E2A;&#x6570;&#x7EC4;&#xFF0C;&#x8981;&#x6C42;&#x5728;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x4E2D;&#x627E;&#x51FA;&#x4EFB;&#x610F;&#x4E00;&#x6BB5;&#x5B50;&#x533A;&#x95F4;&#x7684;&#x548C;&#xFF0C;&#x4F4D;&#x4E8E; [lower,upper] &#x4E4B;&#x95F4;&#x3002;</p>
<p>&#x8FD9;&#x4E00;&#x9898;&#x53EF;&#x4EE5;&#x7528;&#x66B4;&#x529B;&#x89E3;&#x6CD5;&#xFF0C;2 &#x5C42;&#x5FAA;&#x73AF;&#xFF0C;&#x904D;&#x5386;&#x6240;&#x6709;&#x5B50;&#x533A;&#x95F4;&#xFF0C;&#x6C42;&#x548C;&#x5E76;&#x5224;&#x65AD;&#x662F;&#x5426;&#x4F4D;&#x4E8E; [lower,upper] &#x4E4B;&#x95F4;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6; O(n^2) )&#x3002;</p>
<p>&#x8FD9;&#x4E00;&#x9898;&#x5F53;&#x7136;&#x8FD8;&#x6709;&#x66F4;&#x4F18;&#x7684;&#x89E3;&#x6CD5;&#xFF0C;&#x7528;&#x7EBF;&#x6BB5;&#x6811;&#x6216;&#x8005;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#xFF0C;&#x5C06;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x964D;&#x4E3A; O(n log n) &#x3002;&#x9898;&#x76EE;&#x4E2D;&#x8981;&#x6C42; lower &#x2264; sum(i,j) &#x2264; upper&#xFF0C;sum(i,j) = prefixSum(j) - prefixSum(i-1)&#xFF0C;&#x90A3;&#x4E48; lower + prefixSum(i-1) &#x2264; prefixSum(j) &#x2264; upper + prefixSum(i-1)&#x3002;&#x6240;&#x4EE5;&#x5229;&#x7528;&#x524D;&#x7F00;&#x548C;&#x5C06;&#x533A;&#x95F4;&#x548C;&#x8F6C;&#x6362;&#x6210;&#x4E86;&#x524D;&#x7F00;&#x548C;&#x5728;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D; query &#x7684;&#x95EE;&#x9898;&#xFF0C;&#x53EA;&#x4E0D;&#x8FC7;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x7236;&#x8282;&#x70B9;&#x4E2D;&#x5B58;&#x7684;&#x4E0D;&#x662F;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x548C;&#xFF0C;&#x800C;&#x5E94;&#x8BE5;&#x662F;&#x5B50;&#x8282;&#x70B9;&#x51FA;&#x73B0;&#x7684;&#x6B21;&#x6570;&#x3002;&#x7B2C;&#x4E8C;&#x4E2A;&#x8F6C;&#x6362;&#xFF0C;&#x7531;&#x4E8E;&#x524D;&#x7F00;&#x548C;&#x4F1A;&#x5F88;&#x5927;&#xFF0C;&#x6240;&#x4EE5;&#x9700;&#x8981;&#x79BB;&#x6563;&#x5316;&#x3002;&#x4F8B;&#x5982; prefixSum = [-3,-2,-1,0]&#xFF0C;&#x7528;&#x524D;&#x7F00;&#x548C;&#x4E0B;&#x6807;&#x8FDB;&#x884C;&#x79BB;&#x6563;&#x5316;&#xFF0C;&#x6240;&#x4EE5;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x5DE6;&#x53F3;&#x533A;&#x95F4;&#x53D8;&#x6210;&#x4E86; 0-3 &#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121654.png" alt="img"></p>
<p>&#x5229;&#x7528; <code>prefixSum</code> &#x4E0B;&#x6807;&#x79BB;&#x6563;&#x5316;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121702.png" alt=""></p>
<p>&#x8FD8;&#x9700;&#x8981;&#x6CE8;&#x610F;&#x4E00;&#x4E9B;&#x5C0F;&#x7EC6;&#x8282;&#xFF0C;prefixSum &#x8BA1;&#x7B97;&#x5B8C;&#x4EE5;&#x540E;&#x9700;&#x8981;&#x53BB;&#x91CD;&#xFF0C;&#x53BB;&#x91CD;&#x4EE5;&#x540E;&#x5E76;&#x6392;&#x5E8F;&#xFF0C;&#x65B9;&#x4FBF;&#x6784;&#x9020;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x6709;&#x6548;&#x533A;&#x95F4;&#x3002;&#x5982;&#x679C;&#x4E0D;&#x53BB;&#x91CD;&#xFF0C;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x53EF;&#x80FD;&#x51FA;&#x73B0;&#x975E;&#x6CD5;&#x533A;&#x95F4;(left &gt; right)&#x6216;&#x8005;&#x91CD;&#x53E0;&#x533A;&#x95F4;&#x3002;&#x6700;&#x540E;&#x4E00;&#x6B65;&#x5F80;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x5012;&#x5E8F;&#x63D2;&#x5165; prefixSum &#x7684;&#x65F6;&#x5019;&#xFF0C;&#x7528;&#x7684;&#x662F;&#x975E;&#x53BB;&#x91CD;&#x7684;&#xFF0C;&#x63D2;&#x5165; prefixSum[j] &#x4EE3;&#x8868; sum(i,j) &#x4E2D;&#x7684; j&#xFF0C;&#x4F8B;&#x5982;&#x5F80;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x63D2;&#x5165; prefixSum[5]&#xFF0C;&#x4EE3;&#x8868;&#x5F53;&#x524D;&#x6811;&#x4E2D;&#x52A0;&#x5165;&#x4E86; j = 5 &#x7684;&#x60C5;&#x51B5;&#x3002;query &#x64CD;&#x4F5C;&#x5B9E;&#x8D28;&#x662F;&#x5728;&#x505A;&#x533A;&#x95F4;&#x5339;&#x914D;&#xFF0C;&#x4F8B;&#x5982;&#x5F53;&#x524D; i &#x5FAA;&#x73AF;&#x5230; i = 3&#xFF0C;&#x7D2F;&#x8BA1;&#x5F80;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x63D2;&#x5165;&#x4E86; prefixSum[5]&#xFF0C;prefixSum[4]&#xFF0C;prefixSum[3]&#xFF0C;&#x90A3;&#x4E48; query &#x64CD;&#x4F5C;&#x5B9E;&#x8D28;&#x662F;&#x5728;&#x5224;&#x65AD;&#xFF1A;lower &#x2264; sum(i=3,j=3) &#x2264; upper&#xFF0C;lower &#x2264; sum(i=3,j=4) &#x2264; upper&#xFF0C;lower &#x2264; sum(i=3,j=5) &#x2264; upper&#xFF0C;&#x8FD9; 3 &#x4E2A;&#x7B49;&#x5F0F;&#x662F;&#x5426;&#x6210;&#x7ACB;&#xFF0C;&#x6709;&#x51E0;&#x4E2A;&#x6210;&#x7ACB;&#x5C31;&#x8FD4;&#x56DE;&#x51E0;&#x4E2A;&#xFF0C;&#x5373;&#x662F;&#x6700;&#x7EC8;&#x8981;&#x6C42;&#x5F97;&#x7684;&#x7ED3;&#x679C;&#x7684;&#x4E00;&#x90E8;&#x5206;&#x3002;</p>
<p>&#x4E3E;&#x4E2A;&#x4F8B;&#x5B50;&#xFF0C;nums = [-3,1,2,-2,2,-1]&#xFF0C;prefixSum = [-3,-2,0,-2,0,-1]&#xFF0C;&#x53BB;&#x91CD;&#x4EE5;&#x540E;&#x5E76;&#x6392;&#x5E8F;&#x5F97;&#x5230; sum = [-3,-2,-1,0]&#x3002;&#x79BB;&#x6563;&#x5316;&#x6784;&#x9020;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x8FD9;&#x91CC;&#x51FA;&#x4E8E;&#x6F14;&#x793A;&#x7684;&#x65B9;&#x4FBF;&#xFF0C;&#x4E0B;&#x56FE;&#x4E2D;&#x5C31;&#x4E0D;&#x753B;&#x51FA;&#x79BB;&#x6563;&#x540E;&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x4E86;&#xFF0C;&#x7528;&#x975E;&#x79BB;&#x6563;&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x5C55;&#x793A;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121754.png" alt="img"></p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-1 = prefixSum[5] = -1&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121758.png" alt="img"></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[5-1], -1 + prefixSum[5-1]] = [-3,-1]&#xFF0C;&#x5373;&#x5224;&#x65AD; -3 &#x2264; sum(5,5) &#x2264; -1&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x660E;&#x663E;&#x53EA;&#x6709;&#x4E00;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 5&#xFF0C;&#x4E5F;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#xFF0C;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 1&#x3002;</p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-2 = prefixSum[4] = 0&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121803.png" alt="img"></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[4-1], -1 + prefixSum[4-1]] = [-5,-3]&#xFF0C;&#x5373;&#x5224;&#x65AD; -5 &#x2264; sum(4, 4,5) &#x2264; -3&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x6709;&#x4E24;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 4 &#x6216;&#x8005; j = 5&#xFF0C;&#x90FD;&#x4E0D;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#xFF0C;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 0&#x3002;</p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-3 = prefixSum[3] = -2&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121808.png" alt="img"></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[3-1], -1 + prefixSum[3-1]] = [-3,-1]&#xFF0C;&#x5373;&#x5224;&#x65AD; -3 &#x2264; sum(3, 3,4,5) &#x2264; -1&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x6709;&#x4E09;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 3 &#x3001;j = 4 &#x6216;&#x8005; j = 5&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709; j = 3 &#x548C; j = 5&#xFF0C;&#x5373; -3 &#x2264; sum(3, 3) &#x2264; -1 &#x548C; -3 &#x2264; sum(3, 5) &#x2264; -1&#x3002;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 2&#x3002;</p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-4 = prefixSum[2] = 0&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121811.png" alt="img"></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[2-1], -1 + prefixSum[2-1]] = [-5,-3]&#xFF0C;&#x5373;&#x5224;&#x65AD; -5 &#x2264; sum(2, 2,3,4,5) &#x2264; -3&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x6709;&#x56DB;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 2&#x3001; j = 3 &#x3001;j = 4 &#x6216;&#x8005; j = 5&#xFF0C;&#x90FD;&#x4E0D;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x3002;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 0&#x3002;</p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-5 = prefixSum[1] = -2&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121817.png" alt=""></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[1-1], -1 + prefixSum[1-1]] = [-6,-4]&#xFF0C;&#x5373;&#x5224;&#x65AD; -6 &#x2264; sum(1, 1,2,3,4,5) &#x2264; -4&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x6709;&#x4E94;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 1&#x3001; j = 2&#x3001; j = 3 &#x3001;j = 4 &#x6216;&#x8005; j = 5&#xFF0C;&#x90FD;&#x4E0D;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x3002;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 0&#x3002;</p>
<p>&#x5012;&#x5E8F;&#x63D2;&#x5165; len(prefixSum)-6 = prefixSum[0] = -3&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212121822.png" alt=""></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#x67E5;&#x627E;&#x533A;&#x95F4;&#x53D8;&#x4E3A;&#x4E86; [-3 + prefixSum[0-1], -1 + prefixSum[0-1]] = [-3,-1]&#xFF0C;&#x6CE8;&#x610F; prefixSum[-1] = 0&#xFF0C;&#x5373;&#x5224;&#x65AD; -3 &#x2264; sum(0, 0,1,2,3,4,5) &#x2264; -1&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709;&#x51E0;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x8FD9;&#x91CC;&#x6709;&#x516D;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x5373; j = 0&#x3001;j = 1&#x3001;j = 2&#x3001; j = 3 &#x3001;j = 4 &#x6216;&#x8005; j = 5&#xFF0C;&#x6EE1;&#x8DB3;&#x7B49;&#x5F0F;&#x7684;&#x6709; j = 0&#x3001;j = 1&#x3001; j = 3 &#x548C; j = 5&#xFF0C;&#x5373; -3 &#x2264; sum(0, 0) &#x2264; -1 &#x3001; -3 &#x2264; sum(0, 1) &#x2264; -1&#x3001;-3 &#x2264; sum(0, 3) &#x2264; -1 &#x548C; -3 &#x2264; sum(0, 5) &#x2264; -1&#x3002;&#x6240;&#x4EE5;&#x8FD9;&#x4E00;&#x6B65; res = 4&#x3002;&#x6700;&#x540E;&#x7684;&#x7B54;&#x6848;&#x5C31;&#x662F;&#x628A;&#x6BCF;&#x4E00;&#x6B65;&#x7684;&#x7ED3;&#x679C;&#x90FD;&#x7D2F;&#x52A0;&#xFF0C;res = 1 + 0 + 2 + 0 + 0 + 4 = 7&#x3002;</p>
<p>&#x53EF;&#x80FD;&#x4E0A;&#x9762;&#x770B;&#x5B8C;&#x4E86;&#x8FD8;&#x662F;&#x4E91;&#x91CC;&#x96FE;&#x91CC;,&#x6CA1;&#x5173;&#x7CFB;,&#x901A;&#x4FD7;&#x70B9;&#x8BB2;&#x5C31;&#x662F;:</p>
<blockquote>
<p>&#x5148;&#x5BF9;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x533A;&#x95F4;&#x79BB;&#x6563;&#x5316;,v-lower,v-upper&#x4EE3;&#x8868;&#x7684;&#x5C31;&#x662F;&#x533A;&#x95F4;&#x4E2D;&#x7684;&#x6BCF;&#x4E2A;&#x70B9;,&#x8FD9;&#x4E48;&#x505A;&#x7684;&#x76EE;&#x7684;&#x662F;&#x4E3A;&#x4E86;&#x65B9;&#x4FBF;&#x6839;&#x636E;&#x524D;&#x7F00;&#x548C;&#x516C;&#x5F0F;:</p>
<p>lower &#x2264; sum(i,j) &#x2264; upper&#xFF0C;sum(i,j) = prefixSum(j) - prefixSum(i-1),</p>
<p>&#x5BF9;&#x8FD9;&#x4E2A;&#x516C;&#x5F0F;&#x8FDB;&#x884C;&#x53D8;&#x5316;:     prefixSum(j)-upper&lt;= prefixSum(i-1)&lt;=prefixSum(i)-lower</p>
<p>&#x4E5F;&#x5373;,v-lower,v-upper&#x4E5F;&#x5F53;&#x4F5C;&#x8FB9;,&#x662F;&#x4E3A;&#x4E86;&#x6839;&#x636E;&#x4E0A;&#x9762;&#x8FD9;&#x4E2A;&#x516C;&#x5F0F;,&#x6C42;&#x51FA;&#x5171;&#x6709;&#x591A;&#x5C11;&#x7684;&#x70B9;&#x7B26;&#x5408;&#x5728;&#x67D0;&#x4E2A;&#x533A;&#x95F4;&#x5185;</p>
<p>&#x6700;&#x540E;,&#x904D;&#x5386;&#x6BCF;&#x4E2A;prefixSum,&#x5373;&#x53EF;&#x67E5;&#x8BE2;&#x5176;&#x4E4B;&#x524D;&#x80FD;&#x6709;&#x591A;&#x5C11;&#x4E2A;&#x70B9;&#x6EE1;&#x8DB3; prefixSum(j)-upper&lt;= prefixSum(i-1)&lt;=prefixSum(i)-lower</p>
<p>&#x4E5F;&#x5373;,&#x4ECE;&#x7EBF;&#x6BB5;&#x6811;&#x4E2D;&#x67E5;&#x8BE2;&#x533A;&#x95F4;[ prefixSum(j)-upper,prefixSum(i)-lower]&#x7684;&#x6570;&#x91CF;,&#x5C31;&#x662F;&#x6EE1;&#x8DB3;&#x7684;&#x70B9;&#x7684;&#x4E2A;&#x6570;</p>
<p>&#x6700;&#x540E;,&#x628A;&#x8BE5;&#x70B9;&#x63D2;&#x5165;&#x7EBF;&#x6BB5;&#x6811;</p>
</blockquote>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">int</span> arr[<span class="hljs-number">1000000</span>];
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">up</span><span class="hljs-params">(<span class="hljs-keyword">int</span> rt)</span></span>{
        arr[rt]=arr[rt&lt;&lt;<span class="hljs-number">1</span>]+arr[rt&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>];
        <span class="hljs-keyword">return</span>;
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> rt)</span></span>{<span class="hljs-comment">//&#x5EFA;&#x7ACB;&#x533A;&#x95F4;&#x65F6;&#x4EE5;&#x539F;&#x59CB;&#x6570;&#x7EC4;sum&#x7684;&#x5DE6;&#x53F3;&#x7AEF;&#x70B9;&#x4E3A;&#x51C6;&#xFF0C;&#x800C;rt&#x5219;&#x662F;arr&#x7684;&#x4E0B;&#x6807;&#xFF0C;&#x6211;&#x4EEC;&#x67E5;&#x8BE2;&#x66F4;&#x65B0;&#x65F6;&#x4F7F;&#x7528;&#x7684;&#x662F;&#x539F;&#x59CB;&#x6570;&#x7EC4;&#x7684;&#x533A;&#x95F4;&#x3002;</span>
        <span class="hljs-keyword">if</span>(l==r){
            arr[l]=<span class="hljs-number">0</span>;
            <span class="hljs-keyword">return</span>;
        }
        <span class="hljs-keyword">int</span> m=(l+r)/<span class="hljs-number">2</span>;
        build(l,m,rt&lt;&lt;<span class="hljs-number">1</span>);
        build(m+<span class="hljs-number">1</span>,r,rt&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>);
        up(rt);
        <span class="hljs-keyword">return</span>;
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> v,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> rt)</span></span>{
        <span class="hljs-keyword">if</span>(l==r){
            arr[rt]+=v;
            <span class="hljs-keyword">return</span>;
        }
        <span class="hljs-keyword">int</span> m=(l+r)/<span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span>(x&lt;=m)update(x,v,l,m,rt&lt;&lt;<span class="hljs-number">1</span>);
        <span class="hljs-keyword">if</span>(x&gt;m)update(x,v,m+<span class="hljs-number">1</span>,r,rt&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>);
        up(rt);
        <span class="hljs-keyword">return</span>;
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">query</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> rt)</span></span>{
        <span class="hljs-keyword">if</span>(x&lt;=l&amp;&amp;r&lt;=y){
            <span class="hljs-keyword">return</span> arr[rt];
        }
        <span class="hljs-keyword">int</span> m=(l+r)/<span class="hljs-number">2</span>;
        <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">if</span>(x&lt;=m)ans+=query(x,y,l,m,rt&lt;&lt;<span class="hljs-number">1</span>);
        <span class="hljs-keyword">if</span>(y&gt;m)ans+=query(x,y,m+<span class="hljs-number">1</span>,r,rt&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>);
        <span class="hljs-keyword">return</span> ans;
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">countRangeSum</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums, <span class="hljs-keyword">int</span> lower, <span class="hljs-keyword">int</span> upper)</span> </span>{
        <span class="hljs-keyword">int</span> n=nums.size();
        <span class="hljs-comment">//&#x524D;&#x7F00;&#x548C;</span>
        <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> sum[n+<span class="hljs-number">1</span>];
        sum[<span class="hljs-number">0</span>]=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++)sum[i+<span class="hljs-number">1</span>]=sum[i]+nums[i];
        <span class="hljs-comment">//&#x79BB;&#x6563;&#x5316;</span>
        <span class="hljs-comment">//&#x8FD9;&#x91CC;&#x6211;&#x4EEC;&#x7528;&#x5230;&#x7684;&#x503C;&#x5904;&#x7406;&#x524D;&#x7F00;&#x548C;&#x4EE5;&#x5916;&#x8FD8;&#x9700;&#x8981;sum[i]-upper,&#x4EE5;&#x53CA;sum[i]-lower&#x7684;&#x503C;&#xFF0C;&#x6240;&#x4EE5;&#x90FD;&#x9700;&#x8981;&#x8FDB;&#x884C;&#x79BB;&#x6563;&#x5316;</span>
        <span class="hljs-built_in">set</span>&lt;<span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span>&gt; mset;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;=n;i++){
            mset.insert(sum[i]);
            mset.insert(sum[i]-upper);
            mset.insert(sum[i]-lower);
        }
        <span class="hljs-built_in">unordered_map</span>&lt;<span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span>,<span class="hljs-keyword">int</span>&gt; hash;
        <span class="hljs-keyword">int</span> id=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> x:mset){
            hash[x]=id;
            id++;
        }
        <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> m=id<span class="hljs-number">-1</span>;<span class="hljs-comment">//&#x7531;&#x4E8E;&#x6B64;&#x65F6;&#x6211;&#x4EEC;&#x4F7F;&#x7528;&#x7684;&#x662F;&#x79BB;&#x6563;&#x5316;&#x540E;&#x7684;&#x6570;&#x7EC4;&#xFF0C;&#x6240;&#x4EE5;&#x5143;&#x7D20;&#x6570;&#x76EE;&#x4E3A;&#x6240;&#x6709;&#x53EF;&#x80FD;&#x503C;&#x7684;&#x6570;&#x76EE;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;=n;i++){
            ans+=query(hash[sum[i]-upper],hash[sum[i]-lower],<span class="hljs-number">0</span>,m,<span class="hljs-number">1</span>);<span class="hljs-comment">//&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x5185;&#x7684;&#x503C;</span>
            update(hash[sum[i]],<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,m,<span class="hljs-number">1</span>);<span class="hljs-comment">//&#x66F4;&#x65B0;&#x65B0;&#x63D2;&#x5165;&#x7684;&#x503C;</span>
        }
        <span class="hljs-keyword">return</span> ans;

    }
};
</code></pre>
<h3 id="3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;"><a name="3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;" class="anchor-navigation-ex-anchor" href="#3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;" class="plugin-anchor" href="#3&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a>3.<a href="https://leetcode-cn.com/problems/the-skyline-problem/" target="_blank">&#x5929;&#x9645;&#x7EBF;&#x95EE;&#x9898;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212122746.png" alt="image-20201212122746227"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201212122807.png" alt=""></p>
<p><strong>&#x5206;&#x6790;</strong></p>
<p>&#x5982;&#x679C;&#x5B66;&#x8FC7;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x8BDD;,&#x8FD9;&#x9898;&#x4E00;&#x770B;&#x662F;&#x533A;&#x95F4;&#x95EE;&#x9898;,&#x9A6C;&#x4E0A;&#x5E26;&#x4E0A;&#x7EBF;&#x6BB5;&#x6811;&#x6A21;&#x677F;:</p>
<p>&#x7EF4;&#x62A4;&#x533A;&#x95F4;&#x6700;&#x5927;&#x503C;,&#x9700;&#x8981;&#x79BB;&#x6563;&#x5316;,&#x9AD8;&#x5EA6;&#x53D8;&#x5316;,&#x5219;&#x4E3A;&#x5173;&#x952E;&#x70B9;:</p>
<p><a href="https://leetcode-cn.com/problems/the-skyline-problem/submissions/" target="_blank">https://leetcode-cn.com/problems/the-skyline-problem/submissions/</a></p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p)</span>
    </span>{
        tree[p]=max(tree[p*<span class="hljs-number">2</span>],tree[p*<span class="hljs-number">2</span>+<span class="hljs-number">1</span>]);
    }

    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushDown</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p)</span>
    </span>{
        tree[<span class="hljs-number">2</span> * p] = max(tree[<span class="hljs-number">2</span> * p], lazy[p]);
        tree[<span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>] = max(tree[<span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>], lazy[p]);
        lazy[<span class="hljs-number">2</span> * p] = max(lazy[<span class="hljs-number">2</span> * p], lazy[p]) ;
        lazy[<span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>] = max(lazy[<span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>], lazy[p]);
        lazy[p] = <span class="hljs-number">0</span>;
    }

    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> curl, <span class="hljs-keyword">int</span> curr, <span class="hljs-keyword">int</span> p, <span class="hljs-keyword">int</span> v)</span> </span>{
        <span class="hljs-keyword">if</span> (curl &gt;= l &amp;&amp; curr &lt;= r) {
            tree[p] = max(lazy[p], v);
            lazy[p] = max(tree[p], lazy[p]);
            <span class="hljs-keyword">return</span>;
        }
        <span class="hljs-keyword">int</span> mid = (curl + curr) / <span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span> (lazy[p] &gt; <span class="hljs-number">0</span> ) {
            pushDown(p);
        }
        <span class="hljs-keyword">if</span> (l &lt;= mid) update(l, r, curl, mid, <span class="hljs-number">2</span> * p, v);
        <span class="hljs-keyword">if</span> (r &gt; mid) update(l, r, mid + <span class="hljs-number">1</span>, curr, <span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>, v);
        pushUp(p);
    }

    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getsum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> curl, <span class="hljs-keyword">int</span> curr, <span class="hljs-keyword">int</span> p)</span> </span>{
        <span class="hljs-keyword">if</span> (curl &gt;= l &amp;&amp; curr &lt;= r) {
            <span class="hljs-keyword">return</span> max(tree[p], lazy[p]);
        }
        <span class="hljs-keyword">int</span> mid = (curl + curr) / <span class="hljs-number">2</span>;
        <span class="hljs-keyword">int</span> left = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> right = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">if</span> (lazy[p] &gt; <span class="hljs-number">0</span> ) { 
            pushDown(p);
        }
        <span class="hljs-keyword">if</span> (l &lt;= mid) left = getsum(l, r, curl, mid, <span class="hljs-number">2</span>*p);
        <span class="hljs-keyword">if</span> (r &gt; mid) right = getsum(l, r, mid + <span class="hljs-number">1</span>, curr, <span class="hljs-number">2</span> * p + <span class="hljs-number">1</span>);
        <span class="hljs-keyword">return</span> max(left, right);
    }

<span class="hljs-keyword">public</span>:
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; tree;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; lazy;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; getSkyline(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; buildings) {
        <span class="hljs-built_in">set</span>&lt;<span class="hljs-keyword">int</span>&gt; st;
        <span class="hljs-comment">//1.&#x79BB;&#x6563;&#x5316;</span>
        <span class="hljs-built_in">unordered_map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-keyword">int</span>&gt; hash;
        <span class="hljs-built_in">unordered_map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-keyword">int</span>&gt; hashShift;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> building : buildings) {
            st.insert(building[<span class="hljs-number">0</span>]);
            st.insert(building[<span class="hljs-number">1</span>]);
        }
        <span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> it : st) {
            hash[it] = k;
            hashShift[k] = it;
            k++;
        }
        <span class="hljs-keyword">int</span> n = k - <span class="hljs-number">1</span>;
        tree=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        lazy=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        <span class="hljs-comment">//&#x6784;&#x5EFA;&#x7EBF;&#x6BB5;&#x6811;</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> building: buildings) {
            update(hash[building[<span class="hljs-number">0</span>]],  hash[building[<span class="hljs-number">1</span>]]<span class="hljs-number">-1</span>, <span class="hljs-number">1</span>, n, <span class="hljs-number">1</span>, building[<span class="hljs-number">2</span>]); <span class="hljs-comment">//&#x6CE8;&#x610F;-1</span>
        }
        <span class="hljs-comment">//&#x5BF9;&#x6BCF;&#x6761;&#x8FB9;,&#x8FDB;&#x884C;&#x67E5;&#x8BE2;</span>
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; res;
        <span class="hljs-keyword">int</span> before = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= n; i++) {
            <span class="hljs-keyword">int</span> height = getsum(i,i,<span class="hljs-number">1</span>,n,<span class="hljs-number">1</span>);
            <span class="hljs-keyword">if</span> (height != before) { <span class="hljs-comment">//&#x9AD8;&#x5EA6;&#x4E0D;&#x540C;&#x5C31;&#x52A0;&#x5165;</span>
                res.push_back(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;{hashShift[i], height});
            }
            before = height;
        }
        <span class="hljs-keyword">return</span> res;
    }
};
</code></pre>
<h3 id="4&#x7FFB;&#x8F6C;&#x5BF9;"><a name="4&#x7FFB;&#x8F6C;&#x5BF9;" class="anchor-navigation-ex-anchor" href="#4&#x7FFB;&#x8F6C;&#x5BF9;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x7FFB;&#x8F6C;&#x5BF9;" class="plugin-anchor" href="#4&#x7FFB;&#x8F6C;&#x5BF9;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x7FFB;&#x8F6C;&#x5BF9;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201213223821.png" alt="image-20201213223821022"></p>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x672C;&#x4F53;&#x7C7B;&#x4F3C;<strong>&#x533A;&#x95F4;&#x5408;&#x7684;&#x4E2A;&#x6570;</strong></p>
<p>&#x4ECE;&#x8FD9;&#x4E24;&#x9898;&#x7684;&#x5BF9;&#x6BD4;&#x53EF;&#x4EE5;&#x770B;&#x51FA;,&#x7EBF;&#x6BB5;&#x6811;&#x7EF4;&#x62A4;&#x7684;&#x662F;&#x533A;&#x95F4;,&#x6211;&#x4EEC;&#x9700;&#x8981;&#x77E5;&#x9053;&#x6211;&#x4EEC;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x662F;&#x4ECE;&#x54EA;&#x5230;&#x54EA;</p>
<p>&#x6BD4;&#x5982;&#x533A;&#x95F4;&#x548C;&#x4E2A;&#x6570;&#x90A3;&#x9898;,&#x533A;&#x95F4;&#x7684;&#x8303;&#x56F4;&#x662F;:</p>
<p>[ prefixSum(j)-upper,prefixSum(i)-lower]</p>
<p>&#x8FD9;&#x9898;,&#x533A;&#x95F4;&#x7684;&#x8303;&#x56F4;&#x662F;:</p>
<p>pre&gt;cur*2</p>
<p>&#x4E5F;&#x5373;&#x6BD4;&#x5F53;&#x524D;&#x5927;&#x4E24;&#x500D;&#x7684;&#x6570;,&#x5728;&#x4EE3;&#x7801;&#x4E2D;&#x4F53;&#x73B0;&#x4E3A;:</p>
<pre><code>int lower=hash[nums[i]*2]+1;
int upper=hash.size()-1;
ans+=query(1,0,num,lower,upper);
</code></pre><p>&#x4EE3;&#x7801;:</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ls k&lt;&lt;1</span>
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span>  rs k&lt;&lt;1|1</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">int</span> ll;
    <span class="hljs-built_in">vector</span>&lt;ll&gt; tree;
    <span class="hljs-built_in">vector</span>&lt;ll&gt; lazy;
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">reversePairs</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums)</span> </span>{
        <span class="hljs-keyword">int</span> size=nums.size();
        <span class="hljs-keyword">if</span>(size==<span class="hljs-number">0</span>)<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        <span class="hljs-comment">//&#x79BB;&#x6563;&#x5316;</span>
        <span class="hljs-built_in">map</span>&lt;ll,<span class="hljs-keyword">int</span>&gt; hash;
        <span class="hljs-built_in">set</span>&lt;ll&gt; s;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> k:nums)
        {
            s.insert(k);
            s.insert((<span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span>)k*<span class="hljs-number">2</span>);
        }
        <span class="hljs-keyword">int</span> id=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> k:s)
        {
            hash[k]=id++;
        }
        <span class="hljs-comment">//&#x67E5;&#x8BE2;,&#x66F4;&#x65B0;&#x7EBF;&#x6BB5;&#x6811;</span>
        <span class="hljs-keyword">int</span> num=id<span class="hljs-number">-1</span>;
        tree=<span class="hljs-built_in">vector</span>&lt;ll&gt;(num*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;size;i++)
        {
            <span class="hljs-keyword">int</span> lower=hash[(<span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span>)nums[i]*<span class="hljs-number">2</span>]+<span class="hljs-number">1</span>;
            ans+=query(<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,num,lower,num);
            update(<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,num,hash[nums[i]]);
        }
        <span class="hljs-keyword">return</span> ans;
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span>
    </span>{
        tree[k]=tree[ls]+tree[rs];
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> p)</span>
    </span>{
        <span class="hljs-keyword">if</span> (l==r)
        {
           tree[k]++;
        }
        <span class="hljs-keyword">else</span>
        {
            <span class="hljs-keyword">int</span> mid=l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span> (p&lt;=mid)
                update(ls,l,mid,p);
            <span class="hljs-keyword">if</span> (p&gt;mid)
                update(rs,mid+<span class="hljs-number">1</span>,r,p);
            pushUp(k);
        }
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">query</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> L,<span class="hljs-keyword">int</span> R)</span>
    </span>{
        <span class="hljs-keyword">if</span> (l&gt;=L&amp;&amp;r&lt;=R)
        {
            <span class="hljs-keyword">return</span> tree[k];
        }
        <span class="hljs-keyword">else</span>
        {
            <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
            <span class="hljs-keyword">int</span> mid= l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(L&lt;=mid)
                ans+=query(ls,l,mid,L,R);
            <span class="hljs-keyword">if</span>(R&gt;mid)
                ans+=query(rs,mid+<span class="hljs-number">1</span>,r,L,R);
            <span class="hljs-keyword">return</span> ans;
        }
    }
};
</code></pre>
<h2 id="&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;"><a name="&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;" class="anchor-navigation-ex-anchor" href="#&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;" class="plugin-anchor" href="#&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5217;&#x9898;</h2>
<h2 id="&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;"><a name="&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;" class="anchor-navigation-ex-anchor" href="#&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;" class="plugin-anchor" href="#&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x5B57;&#x5178;&#x6811;&#x5217;&#x9898;</h2>
<h3 id="1&#x6A21;&#x677F;&#x9898;&#x76EE;"><a name="1&#x6A21;&#x677F;&#x9898;&#x76EE;" class="anchor-navigation-ex-anchor" href="#1&#x6A21;&#x677F;&#x9898;&#x76EE;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x6A21;&#x677F;&#x9898;&#x76EE;" class="plugin-anchor" href="#1&#x6A21;&#x677F;&#x9898;&#x76EE;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x6A21;&#x677F;&#x9898;&#x76EE;</h3>
<p>&#x5B9A;&#x4E49;&#x7C7B; Trie</p>
<pre><code class="lang-C++"><span class="hljs-keyword">class</span> Trie {
<span class="hljs-keyword">private</span>:
    <span class="hljs-keyword">bool</span> isEnd;
    Trie* next[<span class="hljs-number">26</span>];
<span class="hljs-keyword">public</span>:
    <span class="hljs-comment">//&#x65B9;&#x6CD5;&#x5C06;&#x5728;&#x4E0B;&#x6587;&#x5B9E;&#x73B0;...</span>
};
</code></pre>
<p>&#x63D2;&#x5165;
&#x63CF;&#x8FF0;&#xFF1A;&#x5411; Trie &#x4E2D;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5355;&#x8BCD; word</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x8FD9;&#x4E2A;&#x64CD;&#x4F5C;&#x548C;&#x6784;&#x5EFA;&#x94FE;&#x8868;&#x5F88;&#x50CF;&#x3002;&#x9996;&#x5148;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#x4E0E; word &#x7B2C;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x8FDB;&#x884C;&#x5339;&#x914D;&#xFF0C;&#x4E00;&#x76F4;&#x5339;&#x914D;&#x5230;&#x524D;&#x7F00;&#x94FE;&#x4E0A;&#x6CA1;&#x6709;&#x5BF9;&#x5E94;&#x7684;&#x5B57;&#x7B26;&#xFF0C;&#x8FD9;&#x65F6;&#x5F00;&#x59CB;&#x4E0D;&#x65AD;&#x5F00;&#x8F9F;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;&#x76F4;&#x5230;&#x63D2;&#x5165;&#x5B8C; word &#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x540C;&#x65F6;&#x8FD8;&#x8981;&#x5C06;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;isEnd = true;&#xFF0C;&#x8868;&#x793A;&#x5B83;&#x662F;&#x4E00;&#x4E2A;&#x5355;&#x8BCD;&#x7684;&#x672B;&#x5C3E;&#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        <span class="hljs-keyword">if</span> (node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] == <span class="hljs-literal">NULL</span>) {
            node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] = <span class="hljs-keyword">new</span> Trie();
        }
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
    }
    node-&gt;isEnd = <span class="hljs-literal">true</span>;
}
</code></pre>
<p>&#x67E5;&#x627E;
&#x63CF;&#x8FF0;&#xFF1A;&#x67E5;&#x627E; Trie &#x4E2D;&#x662F;&#x5426;&#x5B58;&#x5728;&#x5355;&#x8BCD; word</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x4E00;&#x76F4;&#x5411;&#x4E0B;&#x5339;&#x914D;&#x5373;&#x53EF;&#xFF0C;&#x5982;&#x679C;&#x51FA;&#x73B0;&#x7ED3;&#x70B9;&#x503C;&#x4E3A;&#x7A7A;&#x5C31;&#x8FD4;&#x56DE; false&#xFF0C;&#x5982;&#x679C;&#x5339;&#x914D;&#x5230;&#x4E86;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x90A3;&#x6211;&#x4EEC;&#x53EA;&#x9700;&#x5224;&#x65AD; node-&gt;isEnd&#x5373;&#x53EF;&#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        node = node-&gt;next[c - <span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> node-&gt;isEnd;
}
</code></pre>
<p>&#x524D;&#x7F00;&#x5339;&#x914D;
&#x63CF;&#x8FF0;&#xFF1A;&#x5224;&#x65AD; Trie &#x4E2D;&#x662F;&#x6216;&#x6709;&#x4EE5; prefix &#x4E3A;&#x524D;&#x7F00;&#x7684;&#x5355;&#x8BCD;</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x548C; search &#x64CD;&#x4F5C;&#x7C7B;&#x4F3C;&#xFF0C;&#x53EA;&#x662F;&#x4E0D;&#x9700;&#x8981;&#x5224;&#x65AD;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x7ED3;&#x70B9;&#x7684;isEnd&#xFF0C;&#x56E0;&#x4E3A;&#x65E2;&#x7136;&#x80FD;&#x5339;&#x914D;&#x5230;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x90A3;&#x540E;&#x9762;&#x4E00;&#x5B9A;&#x6709;&#x5355;&#x8BCD;&#x662F;&#x4EE5;&#x5B83;&#x4E3A;&#x524D;&#x7F00;&#x7684;&#x3002;</p>
<p>C++</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">startsWith</span><span class="hljs-params">(<span class="hljs-built_in">string</span> prefix)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : prefix) {
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
}
&#x5230;&#x8FD9;&#x6211;&#x4EEC;&#x5C31;&#x5DF2;&#x7ECF;&#x5B9E;&#x73B0;&#x4E86;
</code></pre>
<p>&#x5BF9; Trie &#x7684;&#x4E00;&#x4E9B;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x8FD9;&#x6837;&#x6211;&#x4EEC;&#x5BF9; Trie &#x5C31;&#x6709;&#x4E86;&#x8FDB;&#x4E00;&#x6B65;&#x7684;&#x7406;&#x89E3;&#x3002;&#x5B8C;&#x6574;&#x4EE3;&#x7801;&#x6211;&#x8D34;&#x5728;&#x4E86;&#x6587;&#x672B;&#x3002;</p>
<p>&#x603B;&#x7ED3;
&#x901A;&#x8FC7;&#x4EE5;&#x4E0A;&#x4ECB;&#x7ECD;&#x548C;&#x4EE3;&#x7801;&#x5B9E;&#x73B0;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x603B;&#x7ED3;&#x51FA; Trie &#x7684;&#x51E0;&#x70B9;&#x6027;&#x8D28;&#xFF1A;</p>
<p>Trie &#x7684;&#x5F62;&#x72B6;&#x548C;&#x5355;&#x8BCD;&#x7684;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x987A;&#x5E8F;&#x65E0;&#x5173;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x5BF9;&#x4E8E;&#x4EFB;&#x610F;&#x7ED9;&#x5B9A;&#x7684;&#x4E00;&#x7EC4;&#x5355;&#x8BCD;&#xFF0C;Trie &#x7684;&#x5F62;&#x72B6;&#x90FD;&#x662F;&#x552F;&#x4E00;&#x7684;&#x3002;</p>
<p>&#x67E5;&#x627E;&#x6216;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x957F;&#x5EA6;&#x4E3A; L &#x7684;&#x5355;&#x8BCD;&#xFF0C;&#x8BBF;&#x95EE; next &#x6570;&#x7EC4;&#x7684;&#x6B21;&#x6570;&#x6700;&#x591A;&#x4E3A; L+1&#xFF0C;&#x548C; Trie &#x4E2D;&#x5305;&#x542B;&#x591A;&#x5C11;&#x4E2A;&#x5355;&#x8BCD;&#x65E0;&#x5173;&#x3002;</p>
<p>Trie &#x7684;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x4E2D;&#x90FD;&#x4FDD;&#x7559;&#x7740;&#x4E00;&#x4E2A;&#x5B57;&#x6BCD;&#x8868;&#xFF0C;&#x8FD9;&#x662F;&#x5F88;&#x8017;&#x8D39;&#x7A7A;&#x95F4;&#x7684;&#x3002;&#x5982;&#x679C; Trie &#x7684;&#x9AD8;&#x5EA6;&#x4E3A; n&#xFF0C;&#x5B57;&#x6BCD;&#x8868;&#x7684;&#x5927;&#x5C0F;&#x4E3A; m&#xFF0C;&#x6700;&#x574F;&#x7684;&#x60C5;&#x51B5;&#x662F; Trie &#x4E2D;&#x8FD8;&#x4E0D;&#x5B58;&#x5728;&#x524D;&#x7F00;&#x76F8;&#x540C;&#x7684;&#x5355;&#x8BCD;&#xFF0C;&#x90A3;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x4E3A; O(m^n)</p>
<p>&#x6700;&#x597D;&#x60C5;&#x51B5;&#x4E0B;,&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(m)</p>
<p>&#x6700;&#x540E;&#xFF0C;&#x5173;&#x4E8E; Trie &#x7684;&#x5E94;&#x7528;&#x573A;&#x666F;&#xFF0C;&#x5E0C;&#x671B;&#x4F60;&#x80FD;&#x8BB0;&#x4F4F; 8 &#x4E2A;&#x5B57;&#xFF1A;&#x4E00;&#x6B21;&#x5EFA;&#x6811;&#xFF0C;&#x591A;&#x6B21;&#x67E5;&#x8BE2;&#x3002;(&#x6162;&#x6162;&#x9886;&#x609F;&#x53ED;~~)</p>
<p>&#x5168;&#x90E8;&#x4EE3;&#x7801;</p>
<pre><code class="lang-c++">C++

<span class="hljs-keyword">class</span> Trie {
<span class="hljs-keyword">private</span>:
    <span class="hljs-keyword">bool</span> isEnd;
    Trie* next[<span class="hljs-number">26</span>];
<span class="hljs-keyword">public</span>:
    Trie() {
        isEnd = <span class="hljs-literal">false</span>;
        <span class="hljs-built_in">memset</span>(next, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(next));
    }


<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        <span class="hljs-keyword">if</span> (node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] == <span class="hljs-literal">NULL</span>) {
            node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] = <span class="hljs-keyword">new</span> Trie();
        }
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
    }
    node-&gt;isEnd = <span class="hljs-literal">true</span>;
}

<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        node = node-&gt;next[c - <span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> node-&gt;isEnd;
}

<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">startsWith</span><span class="hljs-params">(<span class="hljs-built_in">string</span> prefix)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : prefix) {
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
 }
};
</code></pre>
<h3 id="2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-"><a name="2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-" class="anchor-navigation-ex-anchor" href="#2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-" class="plugin-anchor" href="#2&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD;-"><i class="fa fa-link" aria-hidden="true"></i></a>2.<a href="https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/" target="_blank">&#x6DFB;&#x52A0;&#x4E0E;&#x641C;&#x7D22;&#x5355;&#x8BCD; </a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201214111752.png" alt="image-20201214111752471"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201214111758.png" alt="image-20201214111758625"></p>
<p>&#x8FD9;&#x9898;&#x548C;&#x6A21;&#x677F;&#x9898;&#x7684;&#x533A;&#x522B;&#x53EA;&#x662F;&#x5728;search&#x4E2D;,&#x56E0;&#x4E3A;.&#x53EF;&#x4EE5;&#x66FF;&#x4EE3;&#x6BCF;&#x4E2A;&#x5355;&#x8BCD;,&#x6240;&#x4EE5;&#x9700;&#x8981;&#x7528;&#x5230;&#x56DE;&#x6714;&#x641C;&#x7D22;&#x6CD5;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> WordDictionary {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">typedef</span> WordDictionary Trie;
    <span class="hljs-keyword">bool</span> isEnd;
    Trie * next[<span class="hljs-number">26</span>];
    <span class="hljs-comment">/** Initialize your data structure here. */</span>
    WordDictionary() {
        isEnd= <span class="hljs-literal">false</span>;
        <span class="hljs-built_in">memset</span>(next, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(next));
    }

    <span class="hljs-comment">/** Adds a word into the data structure. */</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">addWord</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
        Trie * node=<span class="hljs-keyword">this</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> k:word)
        {
            <span class="hljs-keyword">int</span> index= k-<span class="hljs-string">&apos;a&apos;</span>;
            <span class="hljs-keyword">if</span>(node-&gt;next[index]==<span class="hljs-literal">NULL</span>)
            {
                node-&gt;next[index]=<span class="hljs-keyword">new</span> Trie();
            }
            node=node-&gt;next[index];
        }
        node-&gt;isEnd= <span class="hljs-literal">true</span>;
    }

    <span class="hljs-comment">/** Returns if the word is in the data structure. A word could contain the dot character &apos;.&apos; to represent any one letter. */</span>
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
        <span class="hljs-keyword">return</span> dfs(word,<span class="hljs-keyword">this</span>);
    }
    <span class="hljs-comment">//&#x56DE;&#x6714;&#x51FD;&#x6570;</span>
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word,Trie * root)</span>
    </span>{
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;word.length();i++)
        {
            <span class="hljs-keyword">char</span> cur=word[i];
            <span class="hljs-keyword">if</span> (cur==<span class="hljs-string">&apos;.&apos;</span>)
            {
               <span class="hljs-built_in">string</span> st=word.substr(i+<span class="hljs-number">1</span>,word.length()); 
               <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;<span class="hljs-number">26</span>;i++)
               {
                   <span class="hljs-comment">//&#x641C;&#x7D22;&#x6BCF;&#x4E00;&#x79CD;&#x53EF;&#x80FD;</span>
                   <span class="hljs-keyword">if</span>(root-&gt;next[i]!=<span class="hljs-literal">NULL</span>)
                   {
                       <span class="hljs-comment">//&#x6210;&#x529F;&#x5C31;&#x76F4;&#x63A5;&#x8FD4;&#x56DE;</span>
                       <span class="hljs-keyword">if</span>(dfs(st,root-&gt;next[i]))<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
                   }
               }
                <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
            }
            <span class="hljs-keyword">else</span>
            {
                <span class="hljs-comment">//&#x5982;&#x679C;&#x4E0D;&#x662F;.,&#x5C31;&#x63A5;&#x7740;&#x8FED;&#x4EE3;&#x5373;&#x53EF;,&#x65E0;&#x9700;&#x56DE;&#x6714;</span>
                <span class="hljs-keyword">int</span> cur=word[i]-<span class="hljs-string">&apos;a&apos;</span>;
                <span class="hljs-keyword">if</span>(root-&gt;next[cur]==<span class="hljs-literal">NULL</span>)<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
                root=root-&gt;next[cur];
            }
        }
        <span class="hljs-keyword">return</span> root-&gt;isEnd;
    }
};

<span class="hljs-comment">/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj-&gt;addWord(word);
 * bool param_2 = obj-&gt;search(word);
 */</span>
</code></pre>
<h3 id="3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii"><a name="3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii" class="anchor-navigation-ex-anchor" href="#3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii" class="plugin-anchor" href="#3&#x5355;&#x8BCD;&#x641C;&#x7D22;-ii"><i class="fa fa-link" aria-hidden="true"></i></a>3.<a href="https://leetcode-cn.com/problems/word-search-ii/" target="_blank">&#x5355;&#x8BCD;&#x641C;&#x7D22; II</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201214112036.png" alt="image-20201214112035985"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201214112043.png" alt="image-20201214112043196"></p>
<p>&#x6839;&#x636E;&#x5B57;&#x5178;&#x6811;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;,&#x5C31;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#x5176;&#x5F88;&#x9002;&#x5408;&#x548C;dfs&#x7B49;&#x7B97;&#x6CD5;&#x8FDB;&#x884C;&#x642D;&#x914D;</p>
<p>&#x672C;&#x9898;&#x5C31;&#x662F;&#x5178;&#x578B;&#x7684;dfs+&#x5B57;&#x5178;&#x6811;</p>
<p>&#x9996;&#x5148;&#x6839;&#x636E;words&#x6784;&#x5EFA;&#x5B57;&#x5178;&#x6811;,&#x5269;&#x4E0B;&#x7684;&#x5C31;&#x662F;dfs&#x7684;&#x6A21;&#x677F;&#x4EE3;&#x7801;&#x4E86;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {

<span class="hljs-keyword">class</span> Trie{
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">bool</span> isEnd;
    Trie * next[<span class="hljs-number">26</span>];
    <span class="hljs-built_in">string</span> word;
    Trie(){
        isEnd= <span class="hljs-literal">false</span>;
        <span class="hljs-built_in">memset</span>(next,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span>(next));
        word=<span class="hljs-string">&quot;&quot;</span>;
    }
};
<span class="hljs-keyword">typedef</span> Trie * node;
<span class="hljs-keyword">public</span>:
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt;result;
    <span class="hljs-keyword">int</span> row;
    <span class="hljs-keyword">int</span> col;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">char</span>&gt;&gt; graph;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; vis;
    <span class="hljs-keyword">int</span> direction [<span class="hljs-number">4</span>][<span class="hljs-number">2</span>]={<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>};
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; findWords(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">char</span>&gt;&gt;&amp; board, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt;&amp; words) {
        <span class="hljs-comment">//&#x521D;&#x59CB;&#x5316;</span>
        row=board.size();
        <span class="hljs-keyword">if</span>(row==<span class="hljs-number">0</span>)
            <span class="hljs-keyword">return</span> result;
        col=board[<span class="hljs-number">0</span>].size();
        <span class="hljs-keyword">this</span>-&gt;graph=board;
        vis=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;(row,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(col,<span class="hljs-number">0</span>));
        <span class="hljs-comment">//&#x5229;&#x7528;word&#x6784;&#x5EFA;&#x5B57;&#x5178;&#x6811;</span>
        node root=<span class="hljs-keyword">new</span> Trie();
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> word:words)
        {
            insert(root,word);
        }
        <span class="hljs-comment">//dfs&#x67E5;&#x8BE2;</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;row;i++)
        {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;col;j++)
            {
                vis[i][j]=<span class="hljs-literal">true</span>;
                dfs(i,j,root);
                vis[i][j]=<span class="hljs-literal">false</span>;
            }
        }
        <span class="hljs-keyword">return</span> result;
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j,node root)</span>
    </span>{
        <span class="hljs-comment">//&#x5339;&#x914D;</span>
        <span class="hljs-keyword">int</span> index= graph[i][j] - <span class="hljs-string">&apos;a&apos;</span>;
        <span class="hljs-keyword">if</span>(root-&gt;next[index]==<span class="hljs-literal">NULL</span>)<span class="hljs-keyword">return</span>;
        root=root-&gt;next[index];
        <span class="hljs-comment">//&#x8FB9;&#x754C;</span>
        <span class="hljs-keyword">if</span>(root-&gt;isEnd)
        {
            result.push_back(root-&gt;word);
            <span class="hljs-comment">//&#x6CE8;&#x610F;&#x8981;&#x8BBE;&#x7F6E;&#x4E3A;false,&#x5426;&#x5219;&#x4F1A;&#x6709;&#x91CD;&#x590D;&#x73B0;&#x8C61;</span>
            root-&gt;isEnd=<span class="hljs-literal">false</span>;
            <span class="hljs-comment">//&#x6CE8;&#x610F;&#x8FD9;&#x91CC;&#x4E0D;&#x80FD;&#x76F4;&#x63A5;return,&#x56E0;&#x4E3A;&#x53EF;&#x80FD;&#x8FD8;&#x4F1A;&#x6709;&#x4EE5;&#x6B64;&#x4E3A;&#x524D;&#x7F00;&#x7684;&#x522B;&#x7684;&#x5355;&#x8BCD;&#x5B58;&#x5728;,&#x9700;&#x8981;&#x7EE7;&#x7EED;&#x641C;&#x7D22;</span>
        }
        <span class="hljs-comment">//&#x56DE;&#x6714;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:direction)
        {
            <span class="hljs-keyword">int</span> x=i+k[<span class="hljs-number">0</span>];
            <span class="hljs-keyword">int</span> y=j+k[<span class="hljs-number">1</span>];
            <span class="hljs-keyword">if</span>(isOk(x,y))
            {
                <span class="hljs-keyword">char</span> cur=graph[x][y];
                vis[x][y]= <span class="hljs-literal">true</span>;
                dfs(x,y,root);
                vis[x][y]= <span class="hljs-literal">false</span>;
            }
        }

    }
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isOk</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span>
    </span>{
        <span class="hljs-keyword">return</span> i&gt;=<span class="hljs-number">0</span>&amp;&amp;j&gt;=<span class="hljs-number">0</span>&amp;&amp;i&lt;row&amp;&amp;j&lt;col&amp;&amp;!vis[i][j];
    }
    <span class="hljs-comment">//&#x63D2;&#x5165;&#x5355;&#x8BCD;&#x5230;&#x5B57;&#x5178;&#x6811;&#x4E2D;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(node root,<span class="hljs-built_in">string</span> word)</span>
    </span>{
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> k:word)
        {
            <span class="hljs-keyword">int</span> index= k-<span class="hljs-string">&apos;a&apos;</span>;
            <span class="hljs-keyword">if</span>(root-&gt;next[index]==<span class="hljs-literal">NULL</span>)
            {
                root-&gt;next[index]=<span class="hljs-keyword">new</span> Trie();
            }
            root=root-&gt;next[index];
        }
        root-&gt;isEnd= <span class="hljs-literal">true</span>;
        root-&gt;word=word;
    }
};
</code></pre>
<h3 id="4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;"><a name="4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;" class="anchor-navigation-ex-anchor" href="#4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;" class="plugin-anchor" href="#4&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;"><i class="fa fa-link" aria-hidden="true"></i></a>4.<a href="https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/" target="_blank">&#x6570;&#x7EC4;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x6700;&#x5927;&#x5F02;&#x6216;&#x503C;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215230031.png" alt="image-20201215230031477"></p>
<h4 id="1hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;"><a name="1hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;" class="anchor-navigation-ex-anchor" href="#1hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;" class="plugin-anchor" href="#1hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>1.Hash&#x6309;&#x4F4D;&#x4E0E;&#x6CD5;</h4>
<p><strong>&#x5F02;&#x6216;&#x8FD0;&#x7B97;&#x7684;&#x6027;&#x8D28;</strong></p>
<p>&#x89E3;&#x51B3;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#xFF0C;&#x6211;&#x4EEC;&#x9996;&#x5148;&#x9700;&#x8981;&#x5229;&#x7528;&#x5F02;&#x6216;&#x8FD0;&#x7B97;&#x7684;&#x4E00;&#x4E2A;&#x6027;&#x8D28;&#xFF1A;</p>
<p>&#x5982;&#x679C; a ^ b = c &#x6210;&#x7ACB;&#xFF0C;&#x90A3;&#x4E48;a ^ c = b &#x4E0E; b ^ c = a &#x5747;&#x6210;&#x7ACB;&#x3002;</p>
<p>&#x5373; &#x5982;&#x679C;&#x6709;&#x4E09;&#x4E2A;&#x6570;&#xFF0C;&#x6EE1;&#x8DB3;&#x5176;&#x4E2D;&#x4E24;&#x4E2A;&#x6570;&#x7684;&#x5F02;&#x6216;&#x503C;&#x7B49;&#x4E8E;&#x53E6;&#x4E00;&#x4E2A;&#x503C;&#xFF0C;&#x90A3;&#x4E48;&#x8FD9;&#x4E09;&#x4E2A;&#x6570;&#x7684;&#x987A;&#x5E8F;&#x53EF;&#x4EE5;&#x4EFB;&#x610F;&#x8C03;&#x6362;&#x3002;</p>
<p>&#xFF08;&#x8BF4;&#x660E;&#xFF1A;&#x5229;&#x7528;&#x8FD9;&#x6761;&#x6027;&#x8D28;&#xFF0C;&#x53EF;&#x4EE5;&#x4E0D;&#x4F7F;&#x7528;&#x7B2C; 3 &#x4E2A;&#x53D8;&#x91CF;&#x800C;&#x4EA4;&#x6362;&#x4E24;&#x4E2A;&#x53D8;&#x91CF;&#x7684;&#x503C;&#x3002;&#xFF09;</p>
<p><strong>&#x5982;&#x4F55;&#x5E94;&#x7528;&#x5230;&#x672C;&#x9898;&#xFF1F;</strong></p>
<p>&#x8FD9;&#x9053;&#x9898;&#x627E;&#x6700;&#x5927;&#x503C;&#x7684;&#x601D;&#x8DEF;&#x662F;&#x8FD9;&#x6837;&#x7684;&#xFF1A;&#x56E0;&#x4E3A;&#x4E24;&#x4E24;&#x5F02;&#x6216;&#x53EF;&#x4EE5;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x503C;&#xFF0C;&#x5728;&#x6240;&#x6709;&#x7684;&#x4E24;&#x4E24;&#x5F02;&#x6216;&#x5F97;&#x5230;&#x7684;&#x503C;&#x4E2D;&#xFF0C;&#x4E00;&#x5B9A;&#x6709;&#x4E00;&#x4E2A;&#x6700;&#x5927;&#x503C;&#xFF0C;&#x6211;&#x4EEC;&#x63A8;&#x6D4B;&#x8FD9;&#x4E2A;&#x6700;&#x5927;&#x503C;&#x5E94;&#x8BE5;&#x662F;&#x4EC0;&#x4E48;&#x6837;&#x7684;&#xFF1F;&#x5373;&#x6839;&#x636E;&#x201C;&#x6700;&#x5927;&#x503C;&#x201D;&#x7684;&#x5B58;&#x5728;&#x6027;&#x89E3;&#x9898;&#xFF08;&#x4E00;&#x5B9A;&#x5B58;&#x5728;&#xFF09;&#x3002;&#x5728;&#x8FD9;&#x91CC;&#x8981;&#x5F3A;&#x8C03;&#x4E00;&#x4E0B;&#xFF1A;</p>
<p>&#x6211;&#x4EEC;&#x53EA;&#x7528;&#x5173;&#x5FC3;&#x8FD9;&#x4E2A;&#x6700;&#x5927;&#x7684;&#x5F02;&#x6216;&#x503C;&#x9700;&#x8981;&#x6EE1;&#x8DB3;&#x4EC0;&#x4E48;&#x6027;&#x8D28;&#xFF0C;&#x8FDB;&#x800C;&#x63A8;&#x51FA;&#x8FD9;&#x4E2A;&#x6700;&#x5927;&#x503C;&#x662F;&#x4EC0;&#x4E48;&#xFF0C;&#x800C;&#x4E0D;&#x5FC5;&#x5173;&#x5FC3;&#x8FD9;&#x4E2A;&#x5F02;&#x6216;&#x503C;&#x662F;&#x7531;&#x54EA;&#x4E24;&#x4E2A;&#x6570;&#x5F97;&#x6765;&#x7684;&#x3002;</p>
<p>&#xFF08;&#x4E0A;&#x9762;&#x8FD9;&#x53E5;&#x8BDD;&#x5F88;&#x91CD;&#x8981;&#xFF0C;&#x5982;&#x679C;&#x8BFB;&#x8005;&#x4E00;&#x5F00;&#x59CB;&#x770B;&#x4E0D;&#x660E;&#x767D;&#x4E0B;&#x9762;&#x7684;&#x601D;&#x8003;&#xFF0C;&#x4E0D;&#x59A8;&#x591A;&#x770B;&#x51E0;&#x904D;&#x6211;&#x4E0A;&#x9762;&#x5199;&#x7684;&#x8FD9;&#x53E5;&#x8BDD;&#x3002;&#xFF09;</p>
<p>&#x4E8E;&#x662F;&#x6709;&#x5982;&#x4E0B;&#x601D;&#x8003;&#xFF1A;</p>
<p>1&#x3001;&#x4E8C;&#x8FDB;&#x5236;&#x4E0B;&#xFF0C;&#x6211;&#x4EEC;&#x5E0C;&#x671B;&#x4E00;&#x4E2A;&#x6570;&#x5C3D;&#x53EF;&#x80FD;&#x5927;&#xFF0C;&#x5373;&#x5E0C;&#x671B;&#x8D8A;&#x9AD8;&#x4F4D;&#x4E0A;&#x8D8A;&#x80FD;&#x591F;&#x51FA;&#x73B0;&#x201C;1&#x201D;&#xFF0C;&#x8FD9;&#x6837;&#x8FD9;&#x4E2A;&#x6570;&#x5C31;&#x662F;&#x6240;&#x6C42;&#x7684;&#x6700;&#x5927;&#x6570;&#xFF0C;&#x8FD9;&#x662F;&#x8D2A;&#x5FC3;&#x7B97;&#x6CD5;&#x7684;&#x601D;&#x60F3;&#x3002;</p>
<p>2&#x3001;&#x4E8E;&#x662F;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x4ECE;&#x6700;&#x9AD8;&#x4F4D;&#x5F00;&#x59CB;&#xFF0C;&#x5230;&#x6700;&#x4F4E;&#x4F4D;&#xFF0C;&#x9996;&#x5148;&#x5047;&#x8BBE;&#x9AD8;&#x4F4D;&#x662F; &#x201C;1&#x201D;&#xFF0C;&#x628A;&#x8FD9; n &#x4E2A;&#x6570;&#x5168;&#x90E8;&#x904D;&#x5386;&#x4E00;&#x904D;&#xFF0C;&#x770B;&#x770B;&#x8FD9;&#x4E00;&#x4F4D;&#x662F;&#x4E0D;&#x662F;&#x771F;&#x7684;&#x53EF;&#x4EE5;&#x662F;&#x201C;1&#x201D;&#xFF0C;&#x5426;&#x5219;&#x8FD9;&#x4E00;&#x4F4D;&#x5C31;&#x5F97;&#x662F;&#x201C;0&#x201D;&#xFF0C;&#x5224;&#x65AD;&#x7684;&#x4F9D;&#x636E;&#x662F;&#x4E0A;&#x9762;&#x201C;&#x5F02;&#x6216;&#x8FD0;&#x7B97;&#x7684;&#x6027;&#x8D28;&#x201D;&#xFF0C;&#x5373;&#x4E0B;&#x9762;&#x7684;&#x7B2C; 3 &#x70B9;&#xFF1B;</p>
<p>3&#x3001;&#x5982;&#x679C; a ^ b = max &#x6210;&#x7ACB; &#xFF0C;max &#x8868;&#x793A;&#x5F53;&#x524D;&#x5F97;&#x5230;&#x7684;&#x201C;&#x6700;&#x5927;&#x503C;&#x201D;&#xFF0C;&#x90A3;&#x4E48;&#x4E00;&#x5B9A;&#x6709; max ^ b = a &#x6210;&#x7ACB;&#x3002;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5148;&#x5047;&#x8BBE;&#x5F53;&#x524D;&#x6570;&#x4F4D;&#x4E0A;&#x7684;&#x503C;&#x4E3A; &#x201C;1&#x201D;&#xFF0C;&#x518D;&#x628A;&#x5F53;&#x524D;&#x5F97;&#x5230;&#x7684;&#x6570;&#x4E0E;&#x8FD9;&#x4E2A; n &#x4E2A;&#x6570;&#x7684; &#x524D;&#x7F00;&#xFF08;&#x56E0;&#x4E3A;&#x662F;&#x4ECE;&#x9AD8;&#x4F4D;&#x5230;&#x4F4E;&#x4F4D;&#x770B;&#xFF0C;&#x6240;&#x4EE5;&#x79F0;&#x4E3A;&#x201C;&#x524D;&#x7F00;&#x201D;&#xFF09;&#x8FDB;&#x884C;&#x5F02;&#x6216;&#x8FD0;&#x7B97;&#xFF0C;&#x653E;&#x5728;&#x4E00;&#x4E2A;&#x54C8;&#x5E0C;&#x8868;&#x4E2D;&#xFF0C;&#x518D;&#x4F9D;&#x6B21;&#x628A;&#x6240;&#x6709; &#x524D;&#x7F00; &#x4E0E;&#x8FD9;&#x4E2A;&#x5047;&#x8BBE;&#x7684;&#x201C;&#x6700;&#x5927;&#x503C;&#x201D;&#x8FDB;&#x884C;&#x5F02;&#x6216;&#x4EE5;&#x540E;&#x5F97;&#x5230;&#x7684;&#x7ED3;&#x679C;&#x653E;&#x5230;&#x54C8;&#x5E0C;&#x8868;&#x91CC;&#x67E5;&#x8BE2;&#x4E00;&#x4E0B;&#xFF0C;&#x5982;&#x679C;&#x67E5;&#x5F97;&#x5230;&#xFF0C;&#x5C31;&#x8BF4;&#x660E;&#x8FD9;&#x4E2A;&#x6570;&#x4F4D;&#x4E0A;&#x53EF;&#x4EE5;&#x662F;&#x201C;1&#x201D;&#xFF0C;&#x5426;&#x5219;&#x5C31;&#x53EA;&#x80FD;&#x662F; 0&#xFF08;&#x770B;&#x8D77;&#x6765;&#x5F88;&#x6655;&#xFF0C;&#x53EF;&#x4EE5;&#x770B;&#x4EE3;&#x7801;&#x7406;&#x89E3;&#xFF09;&#x3002;</p>
<p>&#x4E00;&#x79CD;&#x6781;&#x7AEF;&#x7684;&#x60C5;&#x51B5;&#x662F;&#xFF0C;&#x8FD9; n &#x4E2A;&#x6570;&#x5728;&#x67D0;&#x4E00;&#x4E2A;&#x6570;&#x4F4D;&#x4E0A;&#x5168;&#x90E8;&#x662F; 0 &#xFF0C;&#x90A3;&#x4E48;&#x4EFB;&#x610F;&#x4E24;&#x4E2A;&#x6570;&#x5F02;&#x6216;&#x4EE5;&#x540E;&#x90FD;&#x53EA;&#x80FD;&#x662F; 0&#xFF0C;&#x90A3;&#x4E48;&#x5047;&#x8BBE;&#x5F53;&#x524D;&#x6570;&#x4F4D;&#x662F; 1 &#x8FD9;&#x4EF6;&#x4E8B;&#x60C5;&#x5C31;&#x4E0D;&#x6210;&#x7ACB;&#x3002;</p>
<p><strong>&#x4E3E;&#x4E2A;&#x5217;&#x5B50;:</strong></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215235133.png" alt="image-20201215235133541"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215235140.png" alt="image-20201215235140720"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215235153.png" alt="image-20201215235153122"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215235200.png" alt="image-20201215235200799"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201215235210.png" alt="image-20201215235210443"></p>
<pre><code class="lang-java"><span class="hljs-keyword">import</span> java.util.HashSet;
<span class="hljs-keyword">import</span> java.util.Set;

<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{

    <span class="hljs-comment">// &#x5148;&#x786E;&#x5B9A;&#x9AD8;&#x4F4D;&#xFF0C;&#x518D;&#x786E;&#x5B9A;&#x4F4E;&#x4F4D;&#xFF08;&#x6709;&#x70B9;&#x8D2A;&#x5FC3;&#x7B97;&#x6CD5;&#x7684;&#x610F;&#x601D;&#xFF09;&#xFF0C;&#x624D;&#x80FD;&#x4FDD;&#x8BC1;&#x8FD9;&#x9053;&#x9898;&#x7684;&#x6700;&#x5927;&#x6027;&#x8D28;</span>
    <span class="hljs-comment">// &#x4E00;&#x4F4D;&#x63A5;&#x7740;&#x4E00;&#x4F4D;&#x53BB;&#x786E;&#x5B9A;&#x8FD9;&#x4E2A;&#x6570;&#x4F4D;&#x7684;&#x5927;&#x5C0F;</span>
    <span class="hljs-comment">// &#x5229;&#x7528;&#x6027;&#x8D28;&#xFF1A; a ^ b = c &#xFF0C;&#x5219; a ^ c = b&#xFF0C;&#x4E14; b ^ c = a</span>

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findMaximumXOR</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{
        <span class="hljs-keyword">int</span> res = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> mask = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">30</span>; i &gt;= <span class="hljs-number">0</span>; i--) {
            <span class="hljs-comment">// &#x6CE8;&#x610F;&#x70B9;1&#xFF1A;&#x6CE8;&#x610F;&#x4FDD;&#x7559;&#x524D;&#x7F00;&#x7684;&#x65B9;&#x6CD5;&#xFF0C;mask &#x662F;&#x8FD9;&#x6837;&#x5F97;&#x6765;&#x7684;</span>
            <span class="hljs-comment">// &#x7528;&#x5F02;&#x6216;&#x4E5F;&#x662F;&#x53EF;&#x4EE5;&#x7684; mask = mask ^ (1 &lt;&lt; i);</span>
            mask = mask | (<span class="hljs-number">1</span> &lt;&lt; i);

            <span class="hljs-comment">// System.out.println(Integer.toBinaryString(mask));</span>
            Set&lt;Integer&gt; set = <span class="hljs-keyword">new</span> HashSet&lt;&gt;();
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> num : nums) {
                <span class="hljs-comment">// &#x6CE8;&#x610F;&#x70B9;2&#xFF1A;&#x8FD9;&#x91CC;&#x4F7F;&#x7528; &amp; &#xFF0C;&#x4FDD;&#x7559;&#x524D;&#x7F00;&#x7684;&#x610F;&#x601D;&#xFF08;&#x4ECE;&#x9AD8;&#x4F4D;&#x5230;&#x4F4E;&#x4F4D;&#xFF09;</span>
                set.add(num &amp; mask);
            }

            <span class="hljs-comment">// &#x8FD9;&#x91CC;&#x5148;&#x5047;&#x5B9A;&#x7B2C; n &#x4F4D;&#x4E3A; 1 &#xFF0C;&#x524D; n-1 &#x4F4D; res &#x4E3A;&#x4E4B;&#x524D;&#x8FED;&#x4EE3;&#x6C42;&#x5F97;</span>
            <span class="hljs-keyword">int</span> temp = res | (<span class="hljs-number">1</span> &lt;&lt; i);
            <span class="hljs-keyword">for</span> (Integer prefix : set) {
                <span class="hljs-keyword">if</span> (set.contains(prefix ^ temp)) {
                    res = temp;
                    <span class="hljs-keyword">break</span>;
                }
            }
        }
        <span class="hljs-keyword">return</span> res;
    }
}
</code></pre>
<h4 id="2&#x5B57;&#x5178;&#x6811;"><a name="2&#x5B57;&#x5178;&#x6811;" class="anchor-navigation-ex-anchor" href="#2&#x5B57;&#x5178;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x5B57;&#x5178;&#x6811;" class="plugin-anchor" href="#2&#x5B57;&#x5178;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x5B57;&#x5178;&#x6811;</h4>
<p>&#x5B57;&#x5178;&#x6811;&#x7684;&#x601D;&#x8DEF;&#x5C31;&#x5F88;&#x660E;&#x786E;,&#x540C;&#x6837;&#x628A;&#x6570;&#x5B57;&#x4ECE;&#x9AD8;&#x4F4D;&#x5F00;&#x59CB;&#x63D2;&#x5165;&#x6811;&#x4E2D;&#x6784;&#x5EFA;&#x5B57;&#x5178;&#x6811;,</p>
<p>&#x904D;&#x5386;&#x6BCF;&#x4E2A;&#x6570;,&#x5229;&#x7528;&#x8D2A;&#x5FC3;&#x7684;&#x7B97;&#x6CD5;:</p>
<ul>
<li>&#x5982;&#x679C;&#x5F53;&#x524D;&#x4F4D;&#x4E3A;0,&#x67E5;&#x627E;1</li>
<li>&#x5982;&#x679C;&#x5F53;&#x524D;&#x4F4D;&#x4E3A;1,&#x67E5;&#x627E;0</li>
</ul>
<p>:</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Trie{
<span class="hljs-keyword">public</span>:
    Trie* next[<span class="hljs-number">2</span>];
    Trie()
    {
        <span class="hljs-built_in">memset</span>(next, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(next));
    }
};
<span class="hljs-keyword">class</span> Solution {
    Trie* root = <span class="hljs-keyword">new</span> Trie();
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">findMaximumXOR</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums)</span> </span>{
        <span class="hljs-comment">// &#x5C06;&#x6570;&#x6309;&#x7167;&#x4E8C;&#x8FDB;&#x5236;&#x5F62;&#x5F0F;&#x5168;&#x90E8;&#x5B58;&#x5165;&#x5B57;&#x5178;&#x6811;&#x91CC;&#x9762;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> num : nums)
        {
            Trie* node = root;
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">30</span>; i &gt;= <span class="hljs-number">0</span>; i--)
            {
                <span class="hljs-keyword">int</span> bt = num &gt;&gt; i &amp; <span class="hljs-number">1</span>;
                <span class="hljs-keyword">if</span>(node-&gt;next[bt] == <span class="hljs-literal">nullptr</span>)
                {
                    node-&gt;next[bt] = <span class="hljs-keyword">new</span> Trie();
                }
                node = node-&gt;next[bt];
            }
        }
        <span class="hljs-comment">// &#x627E;&#x6700;&#x5927;^&#x503C;</span>
        <span class="hljs-keyword">int</span> res = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> num : nums)
        {
            Trie* node = root;
            <span class="hljs-keyword">int</span> sum = <span class="hljs-number">0</span>;
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">30</span>; i &gt;= <span class="hljs-number">0</span>; i--)
            {
                <span class="hljs-keyword">int</span> bt = num &gt;&gt; i &amp; <span class="hljs-number">1</span>;  
                <span class="hljs-comment">// &#x5982;&#x679C;bt==1&#x5219;&#x8D2A;&#x5FC3;&#x7684;&#x53BB;&#x627E;0&#x5F02;&#x6216;  &#x5426;&#x5219;&#x627E;1&#x5F02;&#x6216;</span>
                <span class="hljs-keyword">if</span>(bt == <span class="hljs-number">1</span>)
                {
                    sum += node-&gt;next[<span class="hljs-number">0</span>] != <span class="hljs-literal">nullptr</span> ? <span class="hljs-number">1</span> &lt;&lt; i : <span class="hljs-number">0</span> ;
                    node = node-&gt;next[<span class="hljs-number">0</span>] != <span class="hljs-literal">nullptr</span> ? node-&gt;next[<span class="hljs-number">0</span>] : node-&gt;next[<span class="hljs-number">1</span>];
                }
                <span class="hljs-keyword">else</span>
                {
                    sum += node-&gt;next[<span class="hljs-number">1</span>] != <span class="hljs-literal">nullptr</span> ? <span class="hljs-number">1</span> &lt;&lt; i : <span class="hljs-number">0</span> ;
                    node = node-&gt;next[<span class="hljs-number">1</span>] != <span class="hljs-literal">nullptr</span> ? node-&gt;next[<span class="hljs-number">1</span>] : node-&gt;next[<span class="hljs-number">0</span>];
                }
            }
            res = max(res, sum);
        }
        <span class="hljs-keyword">return</span> res;
    }
};
</code></pre>
<h3 id="5&#x56DE;&#x6587;&#x5BF9;"><a name="5&#x56DE;&#x6587;&#x5BF9;" class="anchor-navigation-ex-anchor" href="#5&#x56DE;&#x6587;&#x5BF9;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x56DE;&#x6587;&#x5BF9;" class="plugin-anchor" href="#5&#x56DE;&#x6587;&#x5BF9;"><i class="fa fa-link" aria-hidden="true"></i></a>5.<a href="https://leetcode-cn.com/problems/palindrome-pairs/" target="_blank">&#x56DE;&#x6587;&#x5BF9;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201214120632.png" alt="image-20201214120632053"></p>

<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="6.树论.html" class="navigation navigation-prev " aria-label="Previous page: 6.树论">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="9.模板.html" class="navigation navigation-next " aria-label="Next page: 数据结构模板">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"7.树论例题.md","level":"3.7","depth":1,"next":{"title":"数据结构模板","level":"3.8","depth":1,"path":"数据结构/9.模板.md","ref":"数据结构/9.模板.md","articles":[]},"previous":{"title":"6.树论","level":"3.6","depth":1,"path":"数据结构/6.树论.md","ref":"数据结构/6.树论.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"数据结构/7.树论例题.md","mtime":"2020-12-16T13:07:29.996Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

